A new $1/(1-Ï)$-scaling bound for multiserver queues via a leave-one-out technique
This provides a more interpretable and potentially tighter bound for queueing theory, but it is incremental as it builds on prior work with similar scaling.
The paper tackles the problem of bounding queue length in multisererver queues, presenting a new universal bound of order O(1/(1-ρ)) for G/G/n queues with a simpler proof and often tighter constant, though restricted to light-tailed cases and first moments.
Bounding the queue length in a multiserver queue is a central challenge in queueing theory. Even for the classical $G/G/n$ queue with homogeneous servers, it is highly non-trivial to derive a simple and accurate bound for the steady-state queue length that holds for all problem parameters. A recent breakthrough by Li and Goldberg (2025) establishes a universal bound of order $O(1/(1-Ï))$ that holds for any load $Ï< 1$ and any number of servers $n$. This order is tight in many well-known scaling regimes, including classical heavy-traffic, Halfin-Whitt and Nondegenerate-Slowdown. However, their bounds entail large constant factors and a highly intricate proof, suggesting room for further improvement. In this paper, we present a new universal bound of order $O(1/(1-Ï))$ for the $G/G/n$ queue. Our bound, while restricted to the light-tailed case and the first moment of the queue length, has a more interpretable and often tighter leading constant. Our proof is relatively simple, utilizing a modified $G/G/n$ queue, the stationarity of a quadratic test function, and a novel leave-one-out coupling technique. Finally, we also extend our method to $G/G/n$ queues with fully heterogeneous service-time distributions.