Additive hardness and unbounded configuration gaps in bin packing
Recorded by the registry's curators from GitHub; the authors did not submit it here.
OpenAI
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.
Claims
Files and sources
- Paper
- math @ 1581d4c, source/main.tex ↗
- Posted on GitHub
- 6 October 2026
No verification run is on record for this version.