{"id":"arxiv/2609.03890","url":"https://arxiv.org/abs/2609.03890","tags":["cs.DS","math.OC"],"score":0,"title":"The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing","domain":"cs.DS","source":"arxiv","authors":["Adam Y. Shavit"],"reviews":0,"subject":"cs.DS","summary":"Wang and Sitters' 11/6-approximation for graph balancing (each job allowed on at most two machines) is not one algorithm but a set of permitted executions. Step 1 may return any feasible solution of the fractional relaxation. Step 3 may match remaining jobs to the rounding's slots in many ways. We determine exactly what that latitude permits: ratios arbitrarily close to 11/6, none reaching it, so 11/6 is the least constant bounding every permitted run. We then determine the worst-case guarantee, against the optimum itself, as a function of the big-job threshold beta, the fractional share at…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-03","reactions":{}}