{"id":"arxiv/2611.01369","url":"https://arxiv.org/abs/2611.01369","tags":["cs.DS","math.PR"],"score":0,"title":"Sharper Bounds for Graphical Two-Choice Allocation","domain":"cs.DS","source":"arxiv","authors":["Obinna Okechukwu"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}