One more bin?
A claimed disproof of the modified integer round-up conjecture for bin packing, and NP-hardness of every fixed additive approximation
Covers result 118 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.
5:54. English captions available. The video loads from YouTube when you press play.
Chapters
The claims, in plain words
Bin packing asks how few bins of capacity one can hold a list of items of given sizes. Finding the optimum is NP-hard, yet approximation works remarkably well: Fernandez de la Vega and Lueker came within a factor 1 + ε for large optima, Karmarkar and Karp within an additive O(log² OPT), and Hoberg and Rothvoss, with a randomized algorithm, within an additive O(log OPT). Whether an efficient algorithm could always come within a fixed number of bins of the optimum, even one extra bin, stayed open; Williamson and Shmoys listed it among the open problems in their textbook.
The configuration linear program, in the tradition of Gilmore and Gomory, gives fractional weights to feasible bin patterns so that every item is covered. Its value is a lower bound, and it is remarkably tight. The integer round-up property asks whether the optimum equals that value rounded up; Marcotte found an instance where it fails. The modified integer round-up conjecture of Scheithauer and Terno asserted that the optimum never exceeds the rounded-up value by more than one.
Result 118 is one OpenAI preprint (26 pages, September 24, 2026). Its first theorem: for every whole number c there is an instance, with every item larger than 1/6 (so at most five items per bin), whose configuration value is an integer B, for both the numerical-type and the individual-copy programs, but which needs more than B + c bins. Taking c = 1 disproves the modified conjecture, with no complexity assumption. Its second theorem: for every fixed c it is NP-hard to tell instances that fit in B bins from those that need more than B + c. So a deterministic polynomial-time algorithm that always stays within a fixed number of bins of the optimum exists if and only if P = NP.
What it doesn’t claim
The instances grow very rapidly with c, so the result is compatible with the logarithmic additive algorithms; the paper does not obtain a matching logarithmic lower bound as a function of the instance size. The hardness result is about deterministic algorithms with a fixed additive allowance.
Where it stands
- Posted as a preprint
- OpenAI, 26 pages, dated September 24, 2026
- Peer reviewed
- Not yet
- Checked in Lean
- OpenAI published a Lean proof of both theorems and the equivalence with P = NP; we have not run the check
Last checked October 19, 2026. The preprint has not been revised. OpenAI published a Lean formalization of both theorems and the equivalence with P = NP, matched against its comparator statement, in 284 files and 158,527 lines (not counting Mathlib), including its own formal proof of the needed satisfiability gap, with no unproved steps that we could find. We have not run the check. The paper is not among those OSVerify reviewed, and we have seen no expert review.
How the proof goes
- Two trees that compete. The proof reduces vertex cover to bin packing. Each graph vertex gets a pair of rooted trees with a quota at each depth: each tree on its own can have every root-to-leaf path marked d times within the quotas, but with shared quotas the two cannot both have every path marked even once. The trees become nested interval cells, a plus side and a minus side, and the side that receives the extra global resources records the choice.
- Five items per bin. An intended bin holds a row, an anchor, a global auxiliary, a local auxiliary and a flag, with sizes near 1/5. A row moves from a baseline b to a completion h, and the bin fits exactly when h is no later than the anchor’s deadline z, so the row covers [h, b). Shifting deadlines across a test interval forces extra coverage there; repeated job positions with limited permits force every edge to have a well-funded endpoint, and the funded plus sides form a vertex cover.
- Any packing at all. Integer scores and their conservation leave only boundedly many items outside four five-item patterns, and a second score orders the vertex labels with a per-vertex error independent of the construction’s size. So a cover of size k gives a packing into B bins, and every packing into B + c bins gives a cover of size at most k plus a small fraction of the number of vertices.
- Two consequences. For the gap: the four-vertex clique with k = 2 needs a cover of 3 vertices, more than 2.5, so no packing fits in B + c bins, while an even mixture of the two local states at every vertex gives a fractional solution of value exactly B. For hardness: Håstad’s theorem makes it NP-hard to tell satisfiable 3-SAT formulas from those where at most 15/16 of the clauses can be satisfied, and Karp’s clause graph turns this into a vertex-cover gap.
The numbers in the video
- 600 random instances of 8 to 12 items with sizes between 1/6 and 1/2, solved exactly and with both configuration programs: the optimum never exceeded the rounded-up value; the largest gap was 0.97 of a bin (optimum 4, LP 3.03).
- On all five formulas we tried, the clause graph’s smallest cover equalled 3 times the number of clauses minus the most that can be satisfied, including an unsatisfiable one (17 = 24 − 7).
- The four-vertex clique needs 3 vertices to cover its edges, more than 2 + 4/8 = 2.5.
Read the source
- Additive hardness and unbounded configuration gaps in bin packing (PDF), 26 pages.
- The Lean scope note.
- The collection’s catalog, where this is result 118.
The paper
OpenAI groups related papers into one result; this one has a single paper.
Transcript
Read the full script
0:00Packing bins
Bin packing asks how few bins of capacity one can hold a list of items of given sizes. Finding the optimum is NP-hard, yet approximation works remarkably well. Fernandez de la Vega and Lueker came within a factor 1 + ε for large optima, Karmarkar and Karp within an additive O(log²) of the optimum, and Hoberg and Rothvoss, with a randomized algorithm, within an additive O(log) of the optimum. Whether an efficient algorithm could always come within a fixed number of bins of the optimum, even one extra bin, stayed open; Williamson and Shmoys listed it among the open problems in their textbook. The configuration linear program, in the tradition of Gilmore and Gomory, gives fractional weights to feasible bin patterns so that every item is covered. Its value is a lower bound, and it is remarkably tight. The integer round-up property asks whether the optimum always equals that value rounded up; Marcotte found an instance where it fails. The modified integer round-up conjecture of Scheithauer and Terno asserted that the optimum never exceeds the rounded-up value by more than one. In our check, on 600 random small instances with every item larger than 1/6, the optimum never exceeded the rounded-up value, and the largest gap was 0.97 of a bin.
1:23The claims
Result 118 is one OpenAI preprint, 26 pages, dated September 24. Its first theorem disproves the modified round-up conjecture: for every whole number c, there is an instance whose configuration value is an integer B, but which needs more than B + c bins. Every item is larger than 1/6, so a bin holds at most 5 items, and the same value B holds for the stronger program whose patterns are sets of individual item copies. No complexity assumption is used. Its second theorem: for every fixed c, it is NP-hard to tell instances that fit in B bins from instances that need more than B + c. So a deterministic polynomial-time algorithm that always stays within a fixed number of bins of the optimum exists if and only if P equals NP. The paper notes that its instances grow very rapidly with c, which is compatible with the logarithmic additive algorithms. OpenAI published a Lean formalization of both theorems and the equivalence, 284 files and about 159,000 lines, counting its own imports but not Mathlib, including its own formal proof of the needed satisfiability gap, with a far smaller constant than Håstad’s. We have not run the Lean check ourselves.
2:46How the proof goes
The proof reduces vertex cover to bin packing. For each graph vertex it uses a pair of rooted trees with a quota at each depth. Each tree on its own can have every root-to-leaf path marked d times within the quotas, but when the two trees share the quotas, they cannot both have every path marked even once. The trees become nested interval cells, a plus side and a minus side, and the side that receives the extra global resources records the choice. Each intended bin holds five items: a row, an anchor, a global auxiliary, a local auxiliary and a flag, with sizes near 1/5. In one kind of bin, a row moves from a baseline to a completion coordinate, and the bin fits exactly when the completion comes no later than the anchor’s deadline, so each row covers an interval. Shifting deadlines from the right end of a test interval to its left end forces extra coverage there. Every edge gets repeated job positions with limited permits, so every edge must have a well-funded endpoint, and the funded plus sides form a vertex cover. An arbitrary packing need not use the intended bins. Integer scores and their conservation leave only a bounded number of items outside four five-item patterns, and a second score orders the vertex labels, with an error at each vertex that does not depend on the size of its construction. So every packing into B + c bins yields a vertex cover of size at most k plus a small fraction of the number of vertices, while a cover of size k gives a packing into B bins. For the gap, apply this to the 4-vertex clique with k = 2. Its smallest vertex cover has 3 vertices, more than k plus 1/8 of the 4 vertices, 2.5, so no packing fits in B + c bins, while an even mixture of the two local states at every vertex gives a fractional solution of value exactly B. For hardness, Håstad’s theorem makes it NP-hard to tell satisfiable 3-SAT formulas from those where at most 15/16 of the clauses can be satisfied, and Karp’s clause graph turns this into a vertex-cover gap. In our check, on all five formulas we tried, the clause graph’s smallest cover equalled 3 times the number of clauses minus the most that can be satisfied, including for an unsatisfiable formula.
5:11Where it stands
The preprint is not peer reviewed and has not been revised. The Lean formalization covers the configuration gap for both programs, the NP-hardness for every fixed c, and the equivalence with P equals NP; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, the modified integer round-up conjecture is false, and no efficient deterministic algorithm can guarantee bin packing within a fixed number of extra bins unless P equals NP, settling a question that stayed open alongside the logarithmic additive algorithms.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.