Is the additive integrality gap of the Gilmore–Gomory bin packing LP constant? (Williamson–Shmoys open problem 3: a constant-additive approximation for bin packing)

For one-dimensional bin packing, the best known polynomial-time algorithm (Hoberg and Rothvoss, SODA 2017) computes a packing with at most $\mathrm{OPT}_f+O(\log \mathrm{OPT}_f)$ — and hence at most $\mathrm{OPT}+O(\log \mathrm{OPT})$ — bins by rounding the Gilmore–Gomory configuration LP with discrepancy-theoretic tools; the earlier bounds were $\mathrm{OPT}+O(\log^2 \mathrm{OPT})$ (Karmarkar–Karp, 1982) and $\mathrm{OPT}+O(\log \mathrm{OPT}\cdot\log\log \mathrm{OPT})$ (Rothvoss, 2016). Of the open problems left open by Rothvoss's discrepancy-based paper, the first — reducing the additive error to $O(\log \mathrm{OPT})$ — has been resolved; the surviving open core is whether the additive integrality gap $\mathrm{OPT}-\mathrm{OPT}_f$ of the Gilmore–Gomory LP is bounded by an absolute constant — in constructive form, whether a polynomial-time algorithm can compute a packing with only a constant number of extra bins (Williamson–Shmoys open problem 3) — and conversely whether any superconstant gap exists: the best known lower bound is constant-sized (about 1.1), and $\Omega(\log n)$ is known only as a barrier for support-restricted rounding in the 3-partition regime, not as a bound on the LP gap. Both directions remain open as of August 2026.

Background

One-dimensional bin packing asks for a packing of $n$ items with sizes $s_1,\ldots,s_n \in [0,1]$ into the minimum number $\mathrm{OPT}$ of unit-capacity bins. It is NP-hard, but its asymptotic approximability is settled: Fernandez de la Vega and Lueker gave a polynomial-time algorithm using at most $(1+\varepsilon)\,\mathrm{OPT}+O(1)$ bins for any fixed $\varepsilon>0$ (an asymptotic PTAS, also obtainable from the work of Karmarkar and Karp). The hard frontier is additive (absolute) approximability: how few bins beyond $\mathrm{OPT}$ can a polynomial-time algorithm guarantee?

The standard route is the Gilmore–Gomory configuration LP. A pattern is a multiset of items with total size at most 1, i.e. a feasible content of one bin; the LP has one variable per pattern giving the number of bins packed according to that pattern, subject to covering every item exactly once. It has exponentially many variables but only $n$ constraints, and its optimum $\mathrm{OPT}_f \le \mathrm{OPT}$ can be computed to arbitrary precision in polynomial time via the ellipsoid method with a knapsack separation oracle (column generation). The additive integrality gap $\mathrm{OPT}-\mathrm{OPT}_f$ lower-bounds the additive error of any method that rounds this LP, and its order of magnitude is the central quantitative unknown about it.

Karmarkar and Karp (1982) rounded the LP iteratively to obtain $\mathrm{OPT}+O(\log^2 \mathrm{OPT})$ bins, which stood for three decades. Rothvoss (journal version 2016) improved this to $\mathrm{OPT}_f+O(\log \mathrm{OPT}\cdot\log\log \mathrm{OPT})$ using discrepancy theory: the fractional pattern vector is rounded by a constructive partial-coloring method, which assigns $\pm 1$ colors so that the imbalance against a family of test vectors stays small; feasibility of the resulting bins is exactly such a discrepancy condition. Hoberg and Rothvoss (SODA 2017) then obtained $\mathrm{OPT}_f+O(\log \mathrm{OPT}_f)$ — and therefore $\mathrm{OPT}+O(\log \mathrm{OPT})$ — with a two-stage scheme that first packs items into constant-size containers and then containers into bins. This remains the best known bound; its authors state that it matches certain combinatorial lower bounds and that any further improvement would have to use more algebraic structure.

On the lower-bound side almost nothing is known. The best known lower bound on the additive gap of the configuration LP is constant-sized: Hoberg and Rothvoss record the worst known instance as $\mathrm{OPT}=\mathrm{OPT}_f+1$, and computational searches for cutting stock instances (Kartak–Ripatti 2019) have raised the largest known proper gap only to about 1.1. The modified integer round-up conjecture of Scheithauer and Terno predicts $\mathrm{OPT}\le\lceil \mathrm{OPT}_f\rceil+1$ and has been open since 1997; in the divisible case (bin size an integer multiple of every item size) the gap is known to be at most 4/3 (Martinovic 2022; the earlier bound was 7/5). The only superconstant phenomena known are algorithm-class barriers, not gap lower bounds. Eisenbrand, Pálvölgyi and Rothvoß proved that the additive gap on 3-partition instances (all item sizes in $(1/4,1/2)$, so at most three items fit per bin) is at most six times the discrepancy of three permutations — the set system formed by the intervals of three orderings of $n$ symbols, whose discrepancy Newman, Neiman and Nikolov proved is $\Theta(\log n)$ when refuting Beck's conjecture that it is $O(1)$ — and that the same permutation constructions rule out $o(\log^2 n)$ additive error for any algorithm based on rounding items up (the Karmarkar–Karp class, on instances with arbitrary item sizes), and rule out $o(\log n)$ for integral solutions that only use patterns from the support of the fractional solution in the 3-partition regime. However, those barrier instances have small true gap once arbitrary patterns are allowed, so they do not bound $\mathrm{OPT}-\mathrm{OPT}_f$.

Williamson and Shmoys, in the open-problems chapter of The Design of Approximation Algorithms (2011), list as their third open problem of ten to compute a bin packing with only a constant number of extra bins beyond the optimum, noting that there is no evidence that the Karmarkar–Karp LP relaxation cannot be the basis for such a result. Whether the additive integrality gap of the Gilmore–Gomory LP is constant — and whether it exceeds any constant at all — is the open core left by the discrepancy-based line of work.

Problem Statement

Determine the additive integrality gap of the Gilmore–Gomory configuration LP for one-dimensional bin packing up to constant factors, in both directions.

(1) Constant gap / constant additive approximation (Williamson–Shmoys open problem 3). Prove or refute: there exists an absolute constant $C$ such that (a) every bin packing instance with item sizes in $[0,1]$ satisfies $\mathrm{OPT}\le \mathrm{OPT}_f+C$, where $\mathrm{OPT}_f$ is the optimum of the Gilmore–Gomory configuration LP; or (b) a polynomial-time algorithm computes a feasible packing with at most $\mathrm{OPT}+C$ bins on every instance. Formulation (a) with a constructive rounding yields (b); the two formulations are used interchangeably in the literature, and (b) alone settles the approximability question.

(2) Tightness / lower bound. Prove or refute: there is an infinite family of instances $I_k$ with $\mathrm{OPT}(I_k)-\mathrm{OPT}_f(I_k)\to\infty$. Such a family refutes (1)(a), settles the constant-integrality-gap form of Williamson–Shmoys problem 3 negatively, and rules out a constant additive guarantee for every method whose output is bounded relative to $\mathrm{OPT}_f$ — the route of all known additive approximations, whose guarantees (such as Hoberg and Rothvoss's $\mathrm{OPT}_f+O(\log \mathrm{OPT}_f)$) are stated relative to the LP optimum; it does not by itself refute (1)(b), since the integrality gap of one relaxation does not bound algorithms that bypass it.

Since the statement to refute in (1) is a uniform constant bound, a single finite instance does not suffice, and the unbounded gap must hold for arbitrarily large instances. No restriction on item sizes, multiplicities, or instance structure is permitted: the problem concerns unrestricted bin packing.

References

1. Thomas Rothvoss. Better Bin Packing Approximations via Discrepancy Theory. SIAM Journal on Computing 45(3):930–946, 2016. DOI: 10.1137/140955367. https://doi.org/10.1137/140955367 (journal version of arXiv:1301.4010, https://arxiv.org/abs/1301.4010; arXiv title: Approximating Bin Packing within O(log OPT * log log OPT) bins)
2. Rebecca Hoberg, Thomas Rothvoss. A Logarithmic Additive Integrality Gap for Bin Packing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2616–2625. DOI: 10.1137/1.9781611974782.172. arXiv:1503.08796, https://arxiv.org/abs/1503.08796
3. Narendra Karmarkar, Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), pages 312–320. IEEE, 1982. DOI: 10.1109/SFCS.1982.61. https://doi.org/10.1109/SFCS.1982.61
4. W. Fernandez de la Vega, G. S. Lueker. Bin packing can be solved within 1 + ε in linear time. Combinatorica 1(4):349–355, 1981. DOI: 10.1007/BF02579456. https://doi.org/10.1007/bf02579456
5. P. C. Gilmore, R. E. Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849–859, 1961. DOI: 10.1287/opre.9.6.849. https://doi.org/10.1287/opre.9.6.849
6. David P. Williamson, David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. ISBN 978-0-521-19527-0. DOI: 10.1017/cbo9780511921735. https://www.designofapproxalgs.com/ (Chapter 17, open problem 3)
7. Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß. Bin Packing via Discrepancy of Permutations. ACM Transactions on Algorithms 9(3):1–15, 2013. DOI: 10.1145/2483699.2483704. arXiv:1007.2170, https://arxiv.org/abs/1007.2170
8. Alantha Newman, Ofer Neiman, Aleksandar Nikolov. Beck's Three Permutations Conjecture: A Counterexample and Some Consequences. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pages 253–262. IEEE, 2012. DOI: 10.1109/FOCS.2012.84. https://doi.org/10.1109/FOCS.2012.84
9. Alantha Newman, Aleksandar Nikolov. A counterexample to Beck's conjecture on the discrepancy of three permutations. arXiv:1104.2922, 2011. https://arxiv.org/abs/1104.2922
10. Anish Hebbar, Arindam Khan, K. V. N. Sreenivas. Bin Packing under Random-Order: Breaking the Barrier of 3/2. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024), pages 4177–4219. DOI: 10.1137/1.9781611977912.145. arXiv:2401.04714, https://arxiv.org/abs/2401.04714
11. John Martinovic. A note on the integrality gap of cutting and skiving stock instances. 4OR 20(1):85–104, 2022. DOI: 10.1007/s10288-020-00469-4. https://doi.org/10.1007/s10288-020-00469-4
12. Vadim M. Kartak, Artem V. Ripatti. Large proper gaps in bin packing and dual bin packing problems. Journal of Global Optimization 74(3):467–476, 2019. DOI: 10.1007/s10898-018-0696-0. https://doi.org/10.1007/s10898-018-0696-0
13. Guntram Scheithauer, Johannes Terno. Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem. Operations Research Letters 20(2):93–100, 1997. DOI: 10.1016/S0167-6377(96)00047-8. https://doi.org/10.1016/S0167-6377(96)00047-8
14. Michel X. Goemans, Thomas Rothvoss. Polynomiality for Bin Packing with a Constant Number of Item Types. Journal of the ACM 67(6):1–21, 2020. DOI: 10.1145/3421750. https://doi.org/10.1145/3421750
15. Klaus Jansen, Felix Ohnesorge, Lis Pirotton, Malte Tutas. The Support of Bin Packing is Exponential. arXiv:2512.02758, 2025. https://arxiv.org/abs/2512.02758