Polynomial-time absolute approximation for one-dimensional bin packing (Williamson–Shmoys open problem 3)

One-dimensional bin packing asks for the minimum number OPT of unit-capacity bins into which n items with sizes in [0,1] must be packed. The strongest form of approximation short of exact optimization is an absolute (additive) guarantee: a polynomial-time algorithm that always uses at most OPT + c bins for a fixed constant c. This is open problem 3 in Williamson and Shmoys's The Design of Approximation Algorithms (2011) and is expected to hinge on whether the Gilmore–Gomory configuration LP has a constant additive integrality gap. The best known additive guarantee has progressed from Karmarkar–Karp's OPT + O(log^2 OPT) (1982) to OPT + O(log OPT · log log OPT) (Rothvoss, 2013/2016) to OPT + O(log OPT) (Hoberg–Rothvoss, 2017), which still stands as of August 2026. The only lower bounds are method-class barriers: rounding-up-based methods, including Karmarkar–Karp, cannot beat an additive Omega(log n) on instances with item sizes above 1/4, via a reduction to the discrepancy of three permutations (Eisenbrand–Pálvölgyi–Rothvoß, using Newman–Neiman–Nikolov's counterexample to Beck's three-permutations conjecture). No hardness result rules out OPT + c for any fixed constant c. The problem is open: either exhibit a constant c and a polynomial-time algorithm achieving OPT + c on every instance, or prove that no such absolute approximation exists.

Background

One-dimensional bin packing is a cornerstone problem of combinatorial optimization and of approximation algorithms: given $n$ items with sizes $s_1,\dots,s_n\in[0,1]$, pack them into as few bins of capacity $1$ as possible, and call the minimum number $\mathrm{OPT}$. Deciding whether all items fit into two bins is already NP-hard (it contains the partition problem), so research focuses on approximation. Two strengths of guarantee are distinguished. An asymptotic approximation scheme asks for a solution of value at most $(1+\varepsilon)\mathrm{OPT}+O(1)$; this was achieved in 1981 by de la Vega and Lueker. An absolute (additive) approximation instead asks for a solution within a fixed constant of the optimum. Since every feasible solution has integral value, a guarantee of $\mathrm{OPT}+1$ is the strongest result of this kind possible short of exact optimization, and bin packing is widely regarded as the foremost natural problem for which such a result might still be attainable: Williamson and Shmoys pose exactly this question as Problem 3 in the 'Open Problems' chapter of their textbook The Design of Approximation Algorithms, noting that it had seen no progress in the three decades since Karmarkar and Karp.

The central tool is the configuration LP introduced by Gilmore and Gomory for the cutting-stock problem. A pattern $p$ is a set of items whose sizes sum to at most $1$; the LP is $\min\sum_p x_p$ subject to $\sum_{p\ni i}x_p\ge 1$ for every item $i$, with $x\ge 0$. Its optimum $\mathrm{OPT}_f$ lower-bounds $\mathrm{OPT}$, and the additive integrality gap $\mathrm{OPT}-\mathrm{OPT}_f$ measures how much an LP-rounding algorithm can lose. Karmarkar and Karp (1982) rounded this LP iteratively, grouping item sizes geometrically, and obtained $\mathrm{OPT}+O(\log^2\mathrm{OPT})$ — for three decades the best additive bound. At the structural extreme, the modified integer round-up conjecture of Scheithauer and Terno asserts $\mathrm{OPT}\le\lceil\mathrm{OPT}_f\rceil+1$; it is proven only for instances with at most seven distinct item sizes, no counterexample is known, and no technique is known that could algorithmically exploit such a bound on unrestricted instances.

The post-2010 progress came from discrepancy theory. For a family of sets, the discrepancy is the minimum, over two-colorings of the ground set, of the largest imbalance of any set of the family; the set system of $k$ permutations on $[n]$ consists of all prefixes (intervals) of the permutations. Eisenbrand, Pálvölgyi and Rothvoß proved that for 3-partition instances — all item sizes in $(1/4,1/2)$, so every full bin contains exactly three items — the additive gap of the configuration LP is governed by the discrepancy of three permutations. Beck had conjectured that any three permutations admit a two-coloring with constant imbalance; Newman, Neiman and Nikolov disproved this, constructing three permutations on $n$ symbols that require imbalance $\Omega(\log n)$, thereby settling the quantity at $\Theta(\log n)$. Eisenbrand et al. combined this with their reduction to show that no 'rounding-up'-based method — the class containing Karmarkar–Karp, which selects patterns from the support of a fractional solution and maps each item into the slot of a not-smaller item — can achieve an additive gap of $o(\log n)$ on instances with item sizes above $1/4$, or $o(\log^2 n)$ on arbitrary instances. This is a barrier for one method class, not a lower bound for the problem itself.

Rothvoss then used a constructive discrepancy minimization technique — an algorithmic form of discrepancy theory that outputs the low-discrepancy fractional assignment itself rather than merely proving one exists — to round the configuration LP to $\mathrm{OPT}+O(\log\mathrm{OPT}\cdot\log\log\mathrm{OPT})$ bins (FOCS 2013; journal version in SIAM Journal on Computing, 2016), explicitly presenting this as partial progress on Williamson–Shmoys Problem 3. Hoberg and Rothvoss improved the bound to $\mathrm{OPT}+O(\log\mathrm{OPT})$ via a two-stage packing that first packs items into containers and then packs containers into bins. They observe that this matches the known combinatorial (method-class) lower bounds and that further improvement 'would have to use more algebraic structure'; Rothvoss additionally conjectures that the configuration LP's additive gap is in fact $\Theta(\log n)$. For restricted classes the picture is settled: with a fixed number of distinct item sizes, Jansen and Solis-Oba gave a polynomial-time $\mathrm{OPT}+1$ algorithm, and Goemans and Rothvoss proved the problem is solvable exactly in polynomial time. The open question concerns instances with an unbounded number of distinct item sizes.

Problem Statement

Consider unrestricted one-dimensional bin packing: the input is a list of item sizes $s_1,\dots,s_n\in[0,1]$ given in binary, with no restriction on the number of distinct sizes, and $\mathrm{OPT}$ is the minimum number of unit-capacity bins into which the items can be packed.

Question (Williamson and Shmoys, The Design of Approximation Algorithms, 2011, Open Problem 3): does there exist a constant $c$ and a polynomial-time algorithm that, on every instance, outputs a feasible packing using at most $\mathrm{OPT}+c$ bins?

An affirmative answer must exhibit the algorithm and prove the guarantee for all instances. A negative answer must prove that no polynomial-time algorithm achieves $\mathrm{OPT}+c$ bins for any fixed constant $c$. Results that hold only for a bounded number of distinct item sizes, for a restricted range of item sizes, or for a specific class of algorithms (such as the known $\Omega(\log n)$ barrier for rounding-up methods) do not answer the question.

References

1. 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
2. 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
3. Narendra Karmarkar, Richard M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), pp. 312–320. DOI 10.1109/SFCS.1982.61. https://doi.org/10.1109/SFCS.1982.61
4. 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
5. 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://doi.org/10.1017/CBO9780511921735
6. Friedrich Eisenbrand, Dömötör Pálvölgyi, Thomas Rothvoß, Bin Packing via Discrepancy of Permutations, arXiv:1007.2170 (2010, revised 2012; preliminary version in SODA 2011). https://arxiv.org/abs/1007.2170
7. Alantha Newman, Ofer Neiman, Aleksandar Nikolov, Beck's Three Permutations Conjecture: A Counterexample and Some Consequences, 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 253–262. DOI 10.1109/FOCS.2012.84. https://doi.org/10.1109/FOCS.2012.84
8. 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 (preliminary version in FOCS 2013; preprint published as: Thomas Rothvoss, Approximating Bin Packing within O(log OPT · log log OPT) bins, arXiv:1301.4010. https://arxiv.org/abs/1301.4010)
9. Rebecca Hoberg, Thomas Rothvoss, A Logarithmic Additive Integrality Gap for Bin Packing, Proceedings of the 28th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 2616–2625 (also arXiv:1503.08796). DOI 10.1137/1.9781611974782.172. https://doi.org/10.1137/1.9781611974782.172
10. Klaus Jansen, Roberto Solis-Oba, A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths, Mathematics of Operations Research 36(4):743–753, 2011. DOI 10.1287/moor.1110.0515. https://doi.org/10.1287/moor.1110.0515
11. 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