A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
Abstract
Restricted assignment minimizes makespan, the busiest machine's load, when each job has one size and a set of allowed machines. Its tightest studied relaxation is the configuration linear program, which fractionally gives each machine whole job sets that fit. Its integrality gap, the worst-case ratio of integral optimum to relaxation value, is open in general. On two-weight graph balancing (sizes 1 and 2, each job allowed on at most two machines) the gap is known: Jansen, Land, and Maack (2016) give both bounds. Their Table 1 instance attains 3/2, and their Corollary 11 bound of 2-s/b for sizes s < b matches it at {1,2}. We ask how small such an instance, a witness, can be. We give a six-job witness I* on the complete graph on four machines: unit jobs form a cycle through all four, and two weight-2 jobs take the remaining edges. I* has integral optimum 3 against relaxation value 2, one job fewer than the smallest earlier witness of this class. We prove I* minimum and unique at its size, on any number of machines: no instance with at most five jobs reaches gap 3/2, and at six jobs I* is the only witness, up to relabeling machines and adding unusable machines. At seven jobs uniqueness fails: we classify all thirteen witnesses, including the Jansen-Land-Maack instance. Eight jobs give 154, nine 1,662. At least four machines are necessary. Kartak et al. (2015) classified the extremal non-round-up instances of the same relaxation in one-dimensional cutting stock for small demand; the Discussion relates them. Recognizing witnesses at relaxation value 2, shared by all ours, is coNP-complete, so no min-max characterization with polynomially checkable conditions exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating-point and exact rational arithmetic, with identical results. We accept the pipeline's negatives only after it rediscovers I*.
Related
- Bipolar Fuzzy Minimum-Weight Satisfiability under Continuous t-Norms: A Clause-Witness Branch-and-Bound Framework
- A new perspective in linear Cauchy Elasticity: variational minimum principles for statics, dynamics, and heterogeneous materials
- Minimum Rate For Partially Observable Linear System with Side Information: LQG Plant and Gaussian-Markov Source
- Minimum-Energy Control for Stochastic Linear Systems
- Minimum-Energy Control for Stochastic Linear Systems: A Data-Driven Approach with Finite-Sample Guarantees
BibTeX
@misc{shavit2026minimum,
title = {{A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size}},
author = {Adam Y. Shavit},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.13318},
eprint = {2608.13318},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.13318},
}
RIS
TY - UNPB
TI - A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
AU - Adam Y. Shavit
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2608.13318
UR - https://arxiv.org/abs/2608.13318
AB - Restricted assignment minimizes makespan, the busiest machine's load, when each job has one size and a set of allowed machines. Its tightest studied relaxation is the configuration linear program, which fractionally gives each machine whole job sets that fit. Its integrality gap, the worst-case ratio of integral optimum to relaxation value, is open in general. On two-weight graph balancing (sizes 1 and 2, each job allowed on at most two machines) the gap is known: Jansen, Land, and Maack (2016) give both bounds. Their Table 1 instance attains 3/2, and their Corollary 11 bound of 2-s/b for sizes s < b matches it at {1,2}. We ask how small such an instance, a witness, can be. We give a six-job witness I* on the complete graph on four machines: unit jobs form a cycle through all four, and two weight-2 jobs take the remaining edges. I* has integral optimum 3 against relaxation value 2, one job fewer than the smallest earlier witness of this class. We prove I* minimum and unique at its size, on any number of machines: no instance with at most five jobs reaches gap 3/2, and at six jobs I* is the only witness, up to relabeling machines and adding unusable machines. At seven jobs uniqueness fails: we classify all thirteen witnesses, including the Jansen-Land-Maack instance. Eight jobs give 154, nine 1,662. At least four machines are necessary. Kartak et al. (2015) classified the extremal non-round-up instances of the same relaxation in one-dimensional cutting stock for small demand; the Discussion relates them. Recognizing witnesses at relaxation value 2, shared by all ours, is coNP-complete, so no min-max characterization with polynomially checkable conditions exists unless NP = coNP. Every feasibility decision behind the exhaustive claims was made twice, in floating-point and exact rational arithmetic, with identical results. We accept the pipeline's negatives only after it rediscovers I*.
ER -