Family 118Theoretical computer scienceLeanNot yet digested
Bin packing and unbounded configuration-LP gaps
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.
Manuscripts in this family · 1
Additive hardness and unbounded configuration gaps in bin packing
Sep 24, 2026·Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026.pdfLean
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 bins is NP-hard. Both results hold with rational item sizes greater than 1/6, so each bin contains at most five items.