A new $1/(1-ρ)$-scaling bound for multiserver queues via a leave-one-out technique
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910104020844544 |
|---|---|
| author | Hong, Yige |
| author_facet | Hong, Yige |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_11015 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A new $1/(1-ρ)$-scaling bound for multiserver queues via a leave-one-out technique Hong, Yige Probability Performance 60K25 (Primary) 68M20, 90B22 (Secondary) C.4; G.3; I.6 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. |
| title | A new $1/(1-ρ)$-scaling bound for multiserver queues via a leave-one-out technique |
| topic | Probability Performance 60K25 (Primary) 68M20, 90B22 (Secondary) C.4; G.3; I.6 |
| url | https://arxiv.org/abs/2510.11015 |