Bin Packing: OpenAI Claims the Configuration-LP Gap Has No Limit

About this video

Bin packing asks how few boxes of size 1 can hold a list of items. The configuration LP is the strongest known relaxation: it allows fractions of each way to fill a box, and for decades every known instance needed at most one box more than the LP's value rounded up (the modified integer round-up conjecture). OpenAI claims that the gap between the true optimum and the configuration LP has no limit, and that approximating bin packing within any fixed additive number of boxes is NP-hard, even when every item is larger than 1/6. This is OpenAI's claim and has not yet been peer reviewed.

The animation packs 14 items of sizes 1/2, 2/5, 7/20 and 1/5. Exact search finds the best packing uses 6 boxes; the configuration LP, solved exactly, gives 5.1 boxes with fractional columns. Rounding 5.1 up gives 6, so this toy instance has a small gap. The pink ghost boxes illustrate OpenAI's claim that the gap can grow without bound; they are not OpenAI's instance.

The animation illustrates the result; it is not a proof.

Paper:
- Additive hardness and unbounded configuration gaps in bin packing: github.com/openai/math/blob/main/preprints/Additive-hardness-…

Original visuals (three.js) and synthesized sound: every item lands with a note for its size, and the LP columns ring a chord.

Gradient Damage: mathematics you can see, equations you can hear.
youtube.com/@gradientdamage

Every result explained: gradientdamage.com/p/118