The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing
Abstract
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 or above which Step 2 assigns a job. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We extend the same eligibility rule to 0 < beta <= 1/2, outside the range they state. There a big job's two shares can both reach the threshold, so Step 2 acquires a third choice. We determine it too: exactly 3/2 + (1-beta)floor(1/beta), hence unbounded as beta falls. The worst-case ratio is therefore known at every threshold in (0,1), and attained at none. Consequently 2/3 is the unique optimal threshold, and the guarantee jumps at one half and again at every threshold 1/k below it, rather than degrading smoothly. A companion note examines changes that leave the constant unchanged.
Related
- A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
- Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6
- Symmetric Kahane--Salem--Zygmund Inequalities and the Supremum Norm
- Generalized supremum convolutions on the tensor product of unit intervals: t-conorms and triangle functions
- Asymptotic Rounding Laws for Optimal Thresholds in Secretary Problems
BibTeX
@misc{shavit2026supremum,
title = {{The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing}},
author = {Adam Y. Shavit},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.03890},
eprint = {2609.03890},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03890},
}
RIS
TY - UNPB
TI - The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing
AU - Adam Y. Shavit
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.03890
UR - https://arxiv.org/abs/2609.03890
AB - 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 or above which Step 2 assigns a job. On Wang and Sitters' own range 1/2 < beta < 1 the guarantee is exactly max{3/2 + beta/2, 5/2 - beta}. We extend the same eligibility rule to 0 < beta <= 1/2, outside the range they state. There a big job's two shares can both reach the threshold, so Step 2 acquires a third choice. We determine it too: exactly 3/2 + (1-beta)floor(1/beta), hence unbounded as beta falls. The worst-case ratio is therefore known at every threshold in (0,1), and attained at none. Consequently 2/3 is the unique optimal threshold, and the guarantee jumps at one half and again at every threshold 1/k below it, rather than degrading smoothly. A companion note examines changes that leave the constant unchanged.
ER -