{"id":"openai-math/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing","pdf":"https://github.com/openai/math/blob/main/preprints/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/Additive-hardness-and-unbounded-configuration-gaps-in-bin-packing-September-24-2026","tags":["combinatorial-optimization","bin-packing","complexity-theory"],"score":0,"title":"Additive hardness and unbounded configuration gaps in bin packing","domain":"Theoretical computer science","family":"118","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":true,"family_title":"Bin packing and unbounded configuration-LP gaps"}