Some n by dn linear complementarity problems

The purpose of this paper is to study some recent applications of the n by dn LCP solvable by a parametric principal pivoting algorithm (PPP algorithm). Often, the LCPs arising from these applications give rise to large systems of linear equations which can be solved fairly efficiently by exploiting their special structures. First, it is shown that by analyzing the n by dn LCP we could study the problem of solving a system of equations and the (nonlinear) complementarity problem when the function involved is separable. Next, we examine conditions under which the PPP algorithm is applicable to a general LCP, and then present examples of LCPs arising from various applications satisfying the conditions; included among them is the n by dn LCP with a certain $\text{P}$-property. Finally we study a special class of n by dn LCPs which do not possess the $\text{P}$-property but to which the PPP algorithm is still applicable; a major application of this class of problems is a certain economic spatial equilibrium model with piecewise linear prices.     

The Transform Likelihood Ratio Method for Rare Event Simulation with Heavy Tails

We present a novel method, called the transform likelihood ratio (TLR) method, for estimation of rare event probabilities with heavy-tailed distributions. Via a simple transformation (change of variables) technique the TLR method reduces the original rare event probability estimation with heavy tail distributions to an equivalent one with light tail distributions. Once this transformation has been established we estimate the rare event probability via importance sampling, using the classical exponential change of measure or the standard likelihood ratio change of measure. In the latter case the importance sampling distribution is chosen from the same parametric family as the transformed distribution. We estimate the optimal parameter vector of the importance sampling distribution using the cross-entropy method. We prove the polynomial complexity of the TLR method for certain heavy-tailed models and demonstrate numerically its high efficiency for various heavy-tailed models previously thought to be intractable. We also show that the TLR method can be viewed as a universal tool in the sense that not only it provides a unified view for heavy-tailed simulation but also can be efficiently used in simulation with light-tailed distributions. We present extensive simulation results which support the efficiency of the TLR method.     

Loss probability in an overloaded discrete-time GI/G/1/K system with very large K

We present a simple semi-explicit formula for estimating the loss probability in a discrete-time GI/G/1/K system (with large K) which is operating under an overload condition. The method relaxes the lower boundary and then studies the upper boundary only. The idea is extended to the GI^X/G/1/K system.     

Reliability evaluation of multi-state consecutive k-out-of-r-from-n: G system

This paper proposes a model that generalizes the linear consecutive k-out-of-r-from-n: G system to multi-state case. In this model the system consists of n linearly ordered multi-state components. Both the system and its components can have different states: from complete failure up to perfect functioning. The system is in state j or above if and only if at least k_j components out of r consecutive are in state j or above. An algorithm is provided for evaluating reliability of a special case of multi-state consecutive k-out-of-r-from-n: G system. The algorithm is based on the application of the total probability theorem and on the application of a special case taken from the [Jinsheng Huang, Ming J. Zuo, Member IEEE and Yanhong Wu, Generalized multi-state k-out-of-n: G system, IEEE Trans. Reliab. 49(1) (2000) 105–111.]. Also numerical results of the formerly published test examples and new examples are given.     

Combined m-consecutive and k-out-of-n sliding window systems

This paper proposes a new model that generalizes the linear multi-state sliding window system. In this model the system consists of n linearly ordered multi-state elements. Each element can have different states: from complete failure up to perfect functioning. A performance rate is associated with each state. The system fails if at least one of the following two conditions is met: (1) there exist at least m consecutive overlapping groups of r adjacent elements having the cumulative performance lower than V; (2) there exist at least k arbitrarily located groups of r adjacent elements having the cumulative performance lower than W. An algorithm for system reliability evaluation is suggested which is based on an extended universal moment generating function. Examples of evaluating system reliability and elements’ reliability importance indices are presented. Optimal sequencing of system elements is demonstrated.     

Solving Ck/Cm/1/N queues by using characteristic roots in matrix analytic methods

In this paper, we study a C_k/C_m/1/N open queueing system with finite capacity. We investigate the property which shows that a product of the Laplace Stieltjes Transforms of interarrival and service times distributions satisfies an equation of a simple form. According to this equation, we present that the stationary probabilities on the unboundary states can be written as a linear combination of vector product-forms. Each component of these products is expressed in terms of roots of an associated characteristic polynomial. As a result, we carry out an algorithm for solving stationary probabilities in C_k/C_m/1/N systems, which is independent of N, hence greatly reducing the computational complexity.     

Optimal (d, c) vacation policy for a finite buffer M/M/c queue with unreliable servers and repairs

This paper considers a finite buffer M/M/c queueing system in which servers are unreliable and follow a (d, c) vacation policy. With such a policy, at a service completion instant, if the number of customers is reduced to c − d (c > d), the d idle servers together take a vacation (or leave for a random amount of time doing other secondary job). When these d servers return from a vacation and if still no more than c − d customers are in the system, they will leave for another vacation and so on, until they find at least c − d + 1 customers are in the system at a vacation completion instant, and then they return to serve the queue. This study is motivated by the fact that some practical production and inventory systems or call centers can be modeled as this finite-buffer Markovian queue with unreliable servers and (d, c) vacation policy. Using the Markovian process model, we obtain the stationary distribution of the number of customers in the system numerically. Some cost relationships among several related systems are used to develop a finite search algorithm for the optimal policy (d, c) which maximizes the long-term average profit. Numerical results are presented to illustrate the usefulness of such a algorithm for examining the effects of system parameters on the optimal policy and its associated average profit.     

An O(n log n) unidirectional distributed algorithm for extrema finding in a circle

In this paper we present algorithms, which given a circular arrangement of n uniquely numbered processes, determine the maximum number in a distributive manner. We begin with a simple unidirectional algorithm, in which the number of messages passed is bounded by 2 n log n + O(n). By making several improvements to the simple algorithm, we obtain a unidirectional algorithm in which the number of messages passed is bounded by 1.5nlogn + O(n). These algorithms disprove Hirschberg and Sinclair's conjecture that O(n²) is a lower bound on the number of messages passed in undirectional algorithms for this problem. At the end of the paper we indicate how our methods can be used to improve an algorithm due to Peterson, to obtain a unidirectional algorithm using at most 1.356nlogn + O(n) messages. This is the best bound so far on the number of messages passed in both the bidirectional and unidirectional cases.     

Chaos game representation of the Dst index and prediction of geomagnetic storm events

This paper proposes a two-dimensional chaos game representation (CGR) for the D_st index. The CGR provides an effective method to characterize the multifractality of the D_st time series. The probability measure of this representation is then modeled as a recurrent iterated function system in fractal theory, which leads to an algorithm for prediction of a storm event. We present an analysis and modeling of the D_st time series over the period 1963–2003. The numerical results obtained indicate that the method is useful in predicting storm events one day ahead.     

An O(mn log (nU)) time algorithm to solve the feasibility problem

The phase I maximum flow and most positive cut methods are used to solve the feasibility problem. Both of these methods take one maximum flow computation. Thus the feasibility problem can be solved using maximum flow algorithms. Let n and m be the number of nodes and arcs, respectively. In this paper, we present an algorithm to solve the feasibility problem with integer lower and upper bounds. The running time of our algorithm is O(mn log (nU)), where U is the value of maximum upper bound. Our algorithm improves the O(m² log (nU))-time algorithm in [12]. Hence the current algorithm improves the running time in [12] by a factor of n. Sleator and Goldberg’s algorithm is one of the well-known maximum flow algorithms, which runs in O(mn log n) time, see [5]. Under similarity assumption [11], our algorithm runs in O(mn log n) time, which is the running time of Sleator and Goldberg’s algorithm. The merit of our algorithm is that, in the case of infeasibility of the given network, it not only diagnoses infeasibility but also presents some information that is useful to modeler in estimating the maximum cost of adjusting the infeasible network.     

An O(n2log n) parallel max-flow algorithm

A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented. Its depth is $\text{O(}\text{n}{}^3\text{(}\text{log}\text{n)}\text{p)}$, where p (p ≤ n) is the number of processors used. This problem seems to be more involved than most of the problems for which efficient parallel algorithms exist. The parallel algorithm induces a new rather simple sequential O(n³) algorithm. This algorithm is very much parallel oriented. It is quite difficult to conceive and analyze it, if one is restricted to the sequential point of view.     

A polynomial-time algorithm for computing an optimal admission policy in a GI/M/1/N queue

A polynomial-time algorithm is proposed for computing an optimal admission policy for GI/M/1/N queueing systems. The approach is based upon mathematical programming in which a pointwise minimal value functions is to be found subject to a finite number of DP type constraints. The program is transformed by Fourier-Motzkin elimination into equivalent reduced systems to which a simple, forward-substitution type algorithm can be applied.     

Intrinsic ordering,combinatorial numbers and reliability engineering

A new algorithm for evaluating the top event probability of large fault trees (FTs) is presented. This algorithm does not require any previous qualitative analysis of the FT. Indeed, its efficiency is independent of the FT logic, and it only depends on the number n of basic system components and on their failure probabilities. Our method provides exact lower and upper bounds on the top event probability by using new properties of the intrinsic order relation between binary strings. The intrinsic order enables one to select binary n  -tuples with large occurrence probabilities without necessity to evaluate them. This drastically reduces the complexity of the problem from exponential (2ⁿ$2^n$ binary n-tuples) to linear (n Boolean variables). Our algorithm is mainly based on a recursive formula for rapidly computing the sum of the occurrence probabilities of all binary n-tuples with weight m whose 1s are placed among the k right-most positions. This formula, as well as the balance between accuracy and computational cost, is closely related to the famous Pascal’s triangle.     

An iterative solution method for solving f(A)x = b,using Krylov subspace information obtained for the symmetric positive definite matrix A

The conjugate gradients method generates successive approximations x_i for the solution of the linear system Ax = b, where A is symmetric positive definite and usually sparse. It will be shown how intermediate information obtained by the conjugate gradients (cg) algorithm (or by the closely related Lanczos algorithm) can be used to solve f(A)x = b iteratively in an efficient way, for suitable functions f. The special case f(A) = A² is discussed in particular. We also consider the problem of solving Ax = b for different right-hand sides b. A variant on a well-known algorithm for that problem is proposed, which does not seem to suffer from the usual loss of orthogonality in the standard cg and Lanczos algorithms.     

Derivation of the N-step interdeparture time distribution in GI/G/1 queueing systems

The departure process of a queueing system has been studied since the 1960s. Due to its inherent complexity, closed form solutions for the distribution of the departure process are nearly intractable. In this paper, we derive a closed form expression for the distribution of interdeparture time in a GI/G/1 queueing model. Without loss of generality, we consider an embedded Markov chain in a general K_M/G/1 queueing system, in which the interarrival time distribution is Coxian and service time distribution is general. Closed form solutions of the equilibrium distribution are derived for this model and the Laplace–Stieltjes transform (LST) of the distribution of interdeparture times is presented. An algorithmic computing procedure is given and numerical examples are provided to illustrate the results. With the analysis presented, we provide a novel analytic tool for studying the departure process in a general queueing model.     

Searching for a counterfeit coin with b-balance

We consider the classical problem of searching for a heavier coin in a set of n coins, n-1 of which have the same weight. The weighing device is b-balance which is the generalization of two-arms balance. The minimum numbers of weighings are determined exactly for worst-case sequential algorithm, average-case sequential algorithm, worst-case predetermined algorithm, average-case predetermined algorithm.We also investigate the above search model with additional constraint: each weighing is only allowed to use the coins that are still in doubt. We present a worst-case optimal sequential algorithm and an average-case optimal sequential algorithm requiring the minimum numbers of weighings.     

An adaptive memory algorithm for the k-coloring problem

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.     

Budget-constrained optimal insurance with belief heterogeneity

We re-examine the problem of budget-constrained demand for insurance indemnification when the insured and the insurer disagree about the likelihoods associated with the realizations of the insurable loss. For ease of comparison with the classical literature, we adopt the original setting of Arrow (1971), but allow for divergence in beliefs between the insurer and the insured; and in particular for singularity between these beliefs, that is, disagreement about zero-probability events. We do not impose the no sabotage condition on admissible indemnities. Instead, we impose a state-verification cost that the insurer can incur in order to verify the loss severity, which rules out ex post moral hazard issues that could otherwise arise from possible misreporting of the loss by the insured. Under a mild consistency requirement between these beliefs that is weaker than the Monotone Likelihood Ratio (MLR) condition, we characterize the optimal indemnity and show that it has a simple two-part structure: full insurance on an event to which the insurer assigns zero probability, and a variable deductible on the complement of this event, which depends on the state of the world through a likelihood ratio. The latter is obtained from a Lebesgue decomposition of the insured’s belief with respect to the insurer’s belief.     

Numerical simulation of indoor suspension particles based on v-f model

This paper presents a new algorithm for the prediction of indoor suspension particle dispersion based on a v²-f model. In order to handle the near-wall turbulence anisotropy properly, which is significant in the dispersion of fine particles, the particle eddy diffusivity is calculated using different formulae among regions of the turbulent core and in the vicinity of walls. The new algorithm is validated by several cases performed in two ventilated rooms with various air distribution patterns. The simulation results reveal that v²-f nonlinear turbulence model combined with a particle convective equation gives satisfactory agreement with the experimental data. It is generally found that the dynamic equation combined with the v²-f model can properly handle low Reynolds number (LRN) flows which are usually encountered in indoor air flows and fine particle dispersion.