clopen.solutions

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

SOLUTION CLAIMED OP-00697 — The modified integer round-up conjecture for cutting stock
Counterexample · fidelity not yet established

Files and sources

Paper
math @ 1581d4c, source/main.tex ↗
Posted on GitHub
6 October 2026

No verification run is on record for this version.