Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6
Abstract
Wang and Sitters' rounding scheme for graph balancing (each job allowed on at most two machines) keeps the makespan, the busiest machine's load, within 11/6 of the optimum, and a companion note shows that no smaller constant holds. One suspected cause is Step 3's freedom to match leftover jobs to slots in any valid way. We show that removing that freedom does not improve the constant. An idealized oracle that always picks the valid matching with the smallest makespan still has worst-case constant exactly 11/6 against the optimum. Both natural 7/4 bounds for it, against the relaxation's target and against the optimum, are false. Requiring Step 1 to return a vertex (corner) of the relaxation does not help when that vertex is chosen adversarially. The loss therefore does not come from Step 3's freedom alone. We also prove a reduction confining every overload above 7/4 to two shapes, give a seven-machine instance on which the natural two-phase repair fails, and prove a strict 7/4 bound on the generalized three-path family.
Related
- Hyperbolic Completion of Newton's Off-Center Orbit Problem: Constant-Curvature Rigidity, SO(2,1) Symmetry, and Magnetic Uniqueness
- An improved lower bound for the minimum-autocorrelation constant
- Minimum central circles: an effective characterization of the global asymptotic constant
- Failure of entropic selection for diagonal matrix completion in deep linear networks
- Vanishing discount selection for constant-sign local perturbations of periodic Hamiltonians
BibTeX
@misc{shavit2026minimummakespan,
title = {{Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6}},
author = {Adam Y. Shavit},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.10004},
eprint = {2609.10004},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10004},
}
RIS
TY - UNPB
TI - Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6
AU - Adam Y. Shavit
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.10004
UR - https://arxiv.org/abs/2609.10004
AB - Wang and Sitters' rounding scheme for graph balancing (each job allowed on at most two machines) keeps the makespan, the busiest machine's load, within 11/6 of the optimum, and a companion note shows that no smaller constant holds. One suspected cause is Step 3's freedom to match leftover jobs to slots in any valid way. We show that removing that freedom does not improve the constant. An idealized oracle that always picks the valid matching with the smallest makespan still has worst-case constant exactly 11/6 against the optimum. Both natural 7/4 bounds for it, against the relaxation's target and against the optimum, are false. Requiring Step 1 to return a vertex (corner) of the relaxation does not help when that vertex is chosen adversarially. The loss therefore does not come from Step 3's freedom alone. We also prove a reduction confining every overload above 7/4 to two shapes, give a seven-machine instance on which the natural two-phase repair fails, and prove a strict 7/4 bound on the generalized three-path family.
ER -