An analytical solution for a tandem queue with blocking

The model considered in this paper involves a tandem queue with two waiting lines, and as soon as the second waiting line reaches a certain upper limit, the first line is blocked. Both lines have exponential servers, and arrivals are Poisson. The objective is to determine the joint distribution of both lines in equilibrium. This joint distribution is found by using generalized eigenvalues. Specifically, a simple formula involving the cotangent is derived. The periodicity of the cotangent is then used to determine the location of the majority of the eigenvalues. Once all eigenvalues are found, the eigenvectors can be obtained recursively. The method proposed has a lower computational complexity than all other known methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

乘幂法的改进算法

本文提出了一种改进的乘幂法,一方面大大加快了收敛速度,另一方面可以方便地计算全部的特征值,最后给出一个计算的特征值通用算法。     

An exact depth-first algorithm for the pallet loading problem

This paper proposes a fast exact algorithm to solve the Pallet Loading Problem (PLP) using depth-first strategy. A new concept called Maximal Breadth Filling Sequence (MBFS) is introduced to bring down the size of the search tree. The algorithm makes use of two pruning rules — lower-bound pruning and state-dominance pruning. Although depth-first search, by itself, requires very little memory, the dominance pruning rule makes effective utilization of the available memory. For large problems, more the memory available, more effective is the dominance pruning. The algorithm has been tested on standard problem sets. It has been found to be quite fast in outputting optimal solutions. Empirical findings are given in detail.     

Strong stationary duality for continuous-time Markov chains. Part I: Theory

LetX(t), 0t<, be an ergodic continuous-time Markov chain with finite or countably infinite state space. We construct astrong stationary dual chainX ^* whose first hitting times yield bounds on the convergence to stationarity forX. The development follows closely the discrete-time theory of Diaconis and Fill.^(2,3) However, for applicability it is important that we formulate our results in terms of infinitesimal rates, and this raises new issues.     

An exponential example for Terlaky's pivoting rule for the criss-cross simplex method

Recently T. Terlaky has proposed a new pivoting rule for the criss-cross simplex method for linear programming and he proved that his rule is convergent. In this note we show that the required number of iterations may be exponential in the number of variables and constraints of the problem.     

An efficient shift rule for the prefer-max De Bruijn sequence

A shift rule for the prefer-max De Bruijn sequence is formulated, for all sequence orders, and over any finite alphabet. An efficient algorithm for this shift rule is presented, which has linear (in the sequence order) time and memory complexity.     

An exact formula for the measure dimensions associated with a class of piecewise linear maps

An exact formula for the various measure dimensions of attractors associated with contracting similitudes is given. An example is constructed showing that for more general affine maps the various measure dimensions are not always equal.Communicated by Michael F. Barnsley.     

A central limit theorem for the sojourn times of strongly ergodic Markov chains

Let X_n be an irreducible aperiodic recurrent Markov chain with countable state space I and with the mean recurrence times having second moments. There is proved a global central limit theorem for the properly normalized sojourn times. More precisely, if $\text{t}{}^{\mathrm{(n}}\text{)}{}_{\mathrm{i}}\text{=Σ}{}^{\mathrm{n}}{}_{\mathrm{k=1}}\text{i}\text{?}{}_{\mathrm{i}}\text{(X}{}_{\mathrm{k}}\text{)}$, then the probability measures induced by {t⁽ⁿ⁾_i/√n?√nπ_i}_i?I(π_i being the ergotic distribution) on the Hilbert-space of square summable I-sequences converge weakly in this space to a Gaussian measure determined by a certain weak potential operator.     

An exact formula for the mean number of claims served by a one-channel queuing system with rejections on a given time interval

An exact formula for the mean number of claims served by a one-channel queuing system (QS) with rejections on a given time interval is obtained, which makes it possible, in particular, to calculate exactly the QS efficiency indexes on an arbitrary time interval.     

Speeding up the FMMR perfect sampling algorithm: A case study revisited

In a previous paper by the second author, two Markov chain Monte Carlo perfect sampling algorithms—one called coupling from the past (CFTP) and the other (FMMR) based on rejection sampling—are compared using as a case study the move‐to‐front (MTF) self‐organizing list chain. Here we revisit that case study and, in particular, exploit the dependence of FMMR on the user‐chosen initial state. We give a stochastic monotonicity result for the running time of FMMR applied to MTF and thus identify the initial state that gives the stochastically smallest running time; by contrast, the initial state used in the previous study gives the stochastically largest running time. By changing from worst choice to best choice of initial state we achieve remarkable speedup of FMMR for MTF; for example, we reduce the running time (as measured in Markov chain steps) from exponential in the length n of the list nearly down to n when the items in the list are requested according to a geometric distribution. For this same example, the running time for CFTP grows exponentially in n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003