Analytic approximations of queues with lightly- and heavily-correlated autoregressive service times

We consider a single-server queueing system. The arrival process is modelled as a Poisson process while the service times of the consecutive customers constitute a sequence of autoregressive random variables. Our interest into autoregressive service times comes from the need to capture temporal correlation of the channel conditions on wireless network links. If these fluctuations are slow in comparison with the transmission times of the packets, transmission times of consecutive packets are correlated. Such correlation needs to be taken into account for an accurate performance assessment. By means of a transform approach, we obtain a functional equation for the joint transform of the queue content and the current service time at departure epochs in steady state. To the best of our knowledge, this functional equation cannot be solved by exact mathematical techniques, despite its simplicity. However, by means of a Taylor series expansion in the parameter of the autoregressive process, a “light-correlation” approximation is obtained for performance measures such as moments of the queue content and packet delay. We illustrate our approach by some numerical examples, thereby assessing the accuracy of our approximations by simulation. For the heavy correlation case, we give differential equation approximations based on the time-scale separation technique, and present numerical examples in support of this approximation.     

Matchings in graphs of odd regularity and girth

We establish lower bounds on the matching number of graphs of given odd regularity d$d$ and odd girth g$g$, which are sharp for many values of d$d$ and g$g$. For d=g=5$d=g=5$, we characterize all extremal graphs.     

Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound

We consider a recent branch-and-bound algorithm of the authors for nonconvex quadratic programming. The algorithm is characterized by its use of semidefinite relaxations within a finite branching scheme. In this paper, we specialize the algorithm to the box-constrained case and study its implementation, which is shown to be a state-of-the-art method for globally solving box-constrained nonconvex quadratic programs. S. Burer was supported in part by NSF Grants CCR-0203426 and CCF-0545514.     

Die Projektivitätengruppe der Moulton-Ebenen

The group of projectivities is calculated for the Moulton-Planes M_k, k>1: it does not depend on k and consists of all piecewise projective mappings of the circle onto itself.     

Über das Primzahl-Zwillingsproblem

Ohne Zusammenfassung