Browse › Theoretical computer science › 118 Bin packing and unbounded configuration-LP gaps
Additive hardness and unbounded configuration gaps in bin packing
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We disprove the Modified Integer Round-Up Conjecture for bin packing by constructing instances with arbitrarily large additive gaps between the configuration-LP value and the integral optimum. We also prove that, for every fixed nonnegative integer c, distinguishing instances that fit in B bins from those requiring more than $B+c$ bins is NP-hard. Both results hold with rational item sizes greater than 1/6, so each bin contains at most five items.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Eric Winnington, Unbounded Integrality Gaps and Additive Hardness for the Skiving Stock Problem (GitHub manuscript, 7 October 2026). Transfers this paper's bin-packing construction to the skiving stock problem by complementing item sizes, claiming unbounded additive gaps for the ordinary and proper pattern LPs (refuting Zak's modified integer round-down conjecture) and NP-hardness of fixed additive approximation. The manuscript is conditional on the source result and states that it does not independently re-establish the source proof or its Lean development. [AI-generated per source]
Formalization
- OpenAI math release, Bin packing and unbounded configuration-LP gaps (Lean scope note) (lean/docs/118.md). Describes the scope of the release's Lean formalization: the gap family with $5B$ items and both LP values (individual-copy and size-type configuration LPs) equal to $B$, NP-hardness for each fixed $c$, and the equivalence of deterministic constant-additive approximation with $P=NP$.
- OpenAI, ComparatorChallenges/BinPackingGap.lean (openai/math, commit adc7f12). The comparator statement
main_results(stated withsorry) is a conjunction of four parts: the LP-gap family,PackingGapNPHard cfor allc, the additive-algorithm iffPEqualsNPequivalence, and an exact algorithm underPEqualsNP. - OpenAI, OAI/Computability/BinPacking/Main.lean (openai/math, commit adc7f12). Contains the proof of
OAI.BinPackingGap.main_results, which assembles lemmas from other modules of the development.
Related prior literature mentioned by others
- John Martinovic and Guntram Scheithauer, New theoretical investigations on the gap of the skiving stock problem (Pesquisa Operacional, 2019). The skiving-stock follow-up cites it as a source stating Zak's modified integer round-down conjecture as open, which is the conjecture the follow-up targets with this paper's construction.
- Rebecca Hoberg and Thomas Rothvoss, A Logarithmic Additive Integrality Gap for Bin Packing (arXiv:1503.08796, 2015-03-30). The AI Proved What? exposition cites this logarithmic additive upper bound to explain why the paper's unbounded-gap claim does not supply a matching logarithmic lower bound.
Possibly relevant literature (found by the agent, not checked)
- Christoph Nitsche, Guntram Scheithauer and Johannes Terno, New cases of the cutting stock problem having MIRUP (Mathematical Methods of Operations Research 48(1):105–115, 1998). An earlier paper on instance classes that do satisfy the modified round-up bound that Theorem 1.1 refutes in general.
- Klaus Jansen and Roberto Solis-Oba, An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths (IPCO 2010). An additive-one algorithm for a fixed number of distinct sizes, relating to the paper's remark that its at-most-five-items restriction does not fix the number of distinct sizes, a regime it contrasts with Goemans–Rothvoss.
- Ruixue Yuan, Da Teng and Zhenyu Sun, Additive Rounding for LP-Tight Three-Item Bin Packing (hexagon:2610.00395v1, October 2026). Studies the maximum additive configuration-LP gap for LP-tight instances with sizes in $(1/4,1/2)$ (three items per bin), compared with the five-item-per-bin regime of Theorem 1.1; it does not mention this paper.
Digests and expositions
- AI Proved What?, One more bin? (episode 118, October 2026). The video and transcript explain the two claims and the vertex-cover reduction, distinguish unbounded gaps from a matching logarithmic lower bound, and state that the producers have not run the Lean check. [AI-generated per source]
- Open Mathematics Courses, Configuration gaps in bin packing (online course, undated). Six lessons develop the configuration programs, competing trees, scalar encoding, fractional packing and cover extraction, with proofs and exercises described as written and self-checked by Claude Opus 5.5 and not yet independently reviewed. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- VibeMathed: Problem record
- Emergent Mind: family 118
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026,
author = {{OpenAI}},
title = {{Additive hardness and unbounded configuration gaps in bin packing}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026.pdf}{OAI:Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/118.md. The Lean statements have not been checked by people against the paper's claims.
Family 118: Bin packing and unbounded configuration-LP gaps
Disproves the modified integer round-up conjecture of Scheithauer and Terno: the integral bin-packing optimum can exceed its configuration linear-programming value by an arbitrarily large additive constant. Approximating the optimum within any fixed additive constant is also NP-hard, even when every item exceeds 1/6 and each bin holds at most five items.
This is the only paper in this family.