Metraipolis › archive › dc_c21960be129c
Sharper Bounds for Graphical Two-Choice Allocation — arXiv:2611.01369
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01369
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:35:17.301Z
- SHA-256 of the archived text
7e219ffd6b9c7a0bf8ca3d0291cfef399ad860b6e19e7c6a48a3b31356b37aeb- Stable URL of this page
https://metraipolis.com/documento/dc_c21960be129c
How to cite
Sharper Bounds for Graphical Two-Choice Allocation — arXiv:2611.01369 — arXiv (en), https://arxiv.org/abs/2611.01369 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c21960be129c (Metraipolis archive dc_c21960be129c, sha256 7e219ffd6b9c7a0bf8ca3d0291cfef399ad860b6e19e7c6a48a3b31356b37aeb)
BibTeX
@misc{dcc21960be129c,
title = {Sharper Bounds for Graphical Two-Choice Allocation — arXiv:2611.01369},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01369},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c21960be129c; sha256 7e219ffd6b9c7a0bf8ca3d0291cfef399ad860b6e19e7c6a48a3b31356b37aeb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01369. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In graphical two-choice allocation, vertices are bins, and each arriving ball must be placed irrevocably at one endpoint of a uniformly random edge. The objective is to keep the maximum-minus-minimum load gap small at every time. On cycles, endpoint-local monotone rules incur polynomial gaps at long time horizons, whereas global rules can achieve polylogarithmic gaps. We prove a joint exponential-moment inequality for the orthogonal contrasts of a binary partition tree, controlling all contrasts along a root-to-leaf path simultaneously. Applied to the Bansal--Feldheim strategy, it improves the gap on every $\kappa$-edge-connected $d$-regular graph from $O((d/\kappa)\log^4 n\log\log n)$ to $O((d/\kappa)\log^3 n\log\log n)$. We give an explicit strategy on the $n$-cycle with expected gap $O(\log^2 n)$ uniformly over deterministic times and exponential tails at each such time. An Euler-tour projection yields $O(\bar d\log^2(2M))$ for every connected graph with $M$ edges and degree-proportional capacities. For lower bounds, we introduce a stochastic cut workload: the expected largest normalized overload forced by the requests, plus an indivisibility term. For every online integral strategy, the supremum over time of the expected gap is at least one sixth of this benchmark. Regular rings of cliques attain $\Omega((d/\kappa)\log n)$ along an explicit family, improving the prior additive lower bound. With unequal capacities, the workload need not control the gap: one family has constant relative cut slack, bounded workload and gap $\Omega(\log\log n)$; another has workload at most $20$ but forces gap $\Omega(\log n)$ even for clairvoyant fractional allocations that remain irrevocable. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno). Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Probability (math.PR). Pagina del lavoro: https://arxiv.org/abs/2611.01369 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T11:04:52.297Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).