Given a collection of n points in the plane, the Euclidean matching problem is the task of decomposing the collection into matched pairs connected by line segments in such a way as to minimize the sum of all the segment lengths. The greedy heuristic provides an approximate solution to the Euclidean matching problem by successively matching the two closest unmatched points. We study the behavior of Gn, the sum of the lengths of the segments produced by the greedy heuristic.

We define a notion of order of recurrence for the states and transitions of a general class of time-inhomogeneous Markov chains with transition probabilities proportional to powers of a small vanishing parameter. These orders are shown to satisfy a balance equation across every edge cut in the associated graph. The resulting order balance equations allow computation of the orders of recurrence of the states, and thereby the determination of the asymptotic behavior of the Markov chain.

The method of optimization by simulated annealing is a special case of such Markov processes, and can therefore be treated by means of these balance equations. In particular, in this special situation we show that there holds a detailed balance of order of recurrence across every edge in the graph. Moreover, the sum of the order of recurrence of a state and its cost is shown to be a constant in each connected set of recurrent states. By this approach, we determine the necessary and sufficient condition on the “rate of cooling” to guarantee that a minimum of the optimization problem is hit with probability one. Moreover, the rates of convergence of the probabilities can be deduced from the orders of recurrence.

System components of communication/computer networks are quite reliable in that their average uptimes are much larger than the average repair/replacement time of a failed unit. By taking this observation into account, a semiMarkov model is developed with a simple regenerative structure, thereby providing strong analytical and computational tractability. Expressions of a variety of dynamic performability measures, such as the cumulative system processing capacity and the task completion time, are explicitly derived. Computational procedures for evaluating such time-dependent performability measures are developed based on these theoretical results combined with the Laguerre transform method. The power and the efficiency of the computational procedures are demonstrated through a numerical example.

The unfinished work at arrival instants (FCFS waiting time) can be computed via the LCFS preemptive resume discipline. Analyzing the GI/GI/1 queue in this way gives full interpretation in queuing theoretic language to Feller's analysis of the fluctuations of the random walk. Also, this approach leads naturally to stochastic decompositions for the queue with set-up times, and for other variations of the standard queue. For the M/G/1 queue, the derivations are qualitative, and there are additional connections to branching processes.

This paper derives the steady-state distribution of the virtual wait in GI/M1 queues in which the interarrival times depend on the virtual wait. Applications are queues in which the time it will take for the system to start servicing a new arrival (virtual wait) affects the generation of new arrivals. Such queues arise in airport or large-city freeway traffic control systems. Related state-dependent situations occur in production-inventory systems, cash flow in banking or in insurance systems, dam control systems, and in natural sciences. The method of analysis is by means of system-point level crossing theory.

We show that the calculation of the infinite-horizon value function for a linear/quadratic Markov decision process by policy improvement is exactly equivalent to solution of the equilibrium Riccati equation by the Newton-Raphson method. The assertion extends to risk-sensitive and non-Markov forinulations and thus shows, for example, that the Newton-Raphson method provides an iterative algorithm for the canonical factorization of operators which shows second-order convergence and has a variational basis.

The Coxian-2 distribution is a very useful distribution for queuing and reliability analysis. It is important to know when a general probability distribution can be approximated by a Coxian-2 distribution by fitting the first three moments. For a positive random variable with a squared coefficient of variation larger than 1, a lower bound on its third moment is known for which a three-moment fit exists. To complete the figure, in this note lower and upper bounds on the third moment are derived when the squared coefficient of variation is between 0.5 and 1. Also, we characterize the C2-distributions that correspond to these bounds.

N tasks must be successfully performed for a job to be completed. The tasks may be attempted in any order, where each attempt of task i requires an expected cost ci and is successful with probability pi. Whenever an attempt fails, the job is fed back to the initial stage and the entire sequence starts again. We show that the cost of completing a job is minimized if the tasks are sequenced via increasing values of ci/(l–pi). We further show that the same result holds when the feedback can be either to stage i itself or to the starting task.

In [1] an approach to approximate the transition probabilities and mean occupation times of a continuous-time Markov chain is presented. For the chain under consideration, let Pij(t) and Tij(t) denote respectively the probability that it is in state j at time t, and the total time spent in j by time t, in both cases conditional on the chain starting in state i. Also, let Y1,…, Yn be independent exponential random variables each with rate λ = n/t, which are also independent of the Markov chain.