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)
Manuscript
Additive hardness and unbounded configuration gaps in bin packing
September 24, 2026 · source · Lean formalization available · cite as \cite{OAI:Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026}
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.
Result 118 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md