Bin packing and unbounded configuration-LP gaps

What OpenAI claims

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. (Lean)

Paper

1. Additive hardness and unbounded configuration gaps in bin packing

   24 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's 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.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.