← 研踪 PaperTrailarXiv:2611.01369 · v1
Sharper Bounds for Graphical Two-Choice Allocation
首次提交 2026-11-01 08:10
版本更新 2026-11-01 08:10
雷达观测 2026-11-04 23:43
摘要
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 $κ$-edge-connected $d$-regular graph from $O((d/κ)\log^4 n\log\log n)$ to $O((d/κ)\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 $Ω((d/κ)\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 $Ω(\log\log n)$; another has workload at most $20$ but forces gap $Ω(\log n)$ even for clairvoyant fractional allocations that remain irrevocable.
作者备注：28 pages, 5 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-01 08:10 · 最新观测版本
Sharper Bounds for Graphical Two-Choice Allocation
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 $κ$-edge-connected $d$-regular graph from $O((d/κ)\log^4 n\log\log n)$ to $O((d/κ)\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 $Ω((d/κ)\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 $Ω(\log\log n)$; another has workload at most $20$ but forces gap $Ω(\log n)$ even for clairvoyant fractional allocations that remain irrevocable.
查看此版本解读 →查看此版本原文 ↗