Configuration gaps in bin packing

OpenAI's theorems (2026) that the configuration linear program of bin packing can fall short of the optimum by any additive constant, refuting the modified integer round-up conjecture, and that additive-constant approximation is NP-hard; through competing trees, interval coverage encoded in five-item bins, and a vertex-cover reduction.

Six lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. Bin packing and the configuration program
2. Two competing trees
3. Coordinates, cells and items
4. Sizes that enforce the patterns
5. Packings from covers and a fractional packing
6. Extracting a vertex cover

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• Finite sets, graphs and exact rational arithmetic; the hardness section defines the complexity notions it uses.