1 · The essentials
Bin packing asks how to fit a collection of items into as few fixed-capacity bins as possible. A mathematical shortcut estimates the answer by allowing fractions of possible bin arrangements instead of requiring whole bins. The manuscript constructs cases where the true number of bins exceeds that estimate by an arbitrarily large number. This contradicts the modified integer round-up conjecture of Scheithauer and Terno. The manuscript also shows that allowing any fixed number of extra bins does not remove a fundamental computational difficulty. Both results hold even when every item is larger than one sixth of a bin’s capacity, so no bin can contain more than five items. The main result has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine planning storage using a ledger that lets you buy fractions of different packing arrangements, while the warehouse accepts only whole bins. The result says the ledger’s estimate can fall short of the bins actually needed by an arbitrarily large number, even when each bin holds only a few items.
Why it matters
The configuration-LP estimate cannot always be turned into the true optimum by adding a fixed allowance of bins. Separately, the hardness result says that distinguishing packings within any fixed additive allowance is NP-hard. The restriction to at most five items per bin shows that neither conclusion requires bins containing many tiny items.
2 · Going further
The problem compares the integral bin-packing optimum—the minimum number of whole bins needed—with the configuration linear-programming value, a relaxation that allows fractional use of feasible bin configurations. The main manuscript constructs instances for which the additive difference between these values is arbitrarily large. The source identifies this as a disproof of the modified integer round-up conjecture of Scheithauer and Terno.
The computational statement has an explicit gap: for every fixed nonnegative integer , distinguishing instances that fit in bins from instances requiring more than bins is NP-hard. Both this statement and the unbounded configuration-LP gap hold for rational item sizes greater than , with bin capacity normalized to one. Consequently, every feasible bin contains at most five items.
The abstract describes the gap result as a construction of instances, but supplies no details of that construction or of the hardness argument. Only one manuscript is supplied, so no relationship to companion manuscripts can be described. The main result has a Lean formalization; the supplied description does not separately specify which supporting claims or hardness steps are included in its scope.
Useful notions
- Minimum-bin packing
- Whole-number versus fractional choices
- Linear-programming relaxations
- Additive approximation error
- NP-hardness
What was known before / what is new
Before
The source names the modified integer round-up conjecture of Scheithauer and Terno as the conjecture being challenged. It provides no earlier bounds, chronology, or account of previous approaches.
New
The manuscript presents instances with arbitrarily large additive differences between the configuration-LP value and the integral optimum. It also shows in the manuscript that, for every fixed nonnegative integer , distinguishing feasibility in bins from a requirement of more than bins is NP-hard. Both results retain rational item sizes greater than .
Limits and assumptions
The stated results hold even under the restriction to rational item sizes greater than one sixth of bin capacity; this permits at most five items per bin. The gap is additive, and the source does not state a multiplicative-gap result. The hardness statement concerns every fixed nonnegative integer allowance, not an allowance that grows with the instance. The main result has a Lean formalization, but the source does not give a claim-by-claim verification scope. No remaining open questions or construction details are supplied.
Mini glossary
- Integral optimum —
- The smallest number of whole bins needed to pack all the items.
- Configuration —
- A collection of items that can fit together in one bin.
- Configuration LP —
- A linear-programming relaxation of bin packing that allows fractional use of feasible bin configurations.
- Additive gap —
- The difference between the integral optimum and the configuration-LP value.
- NP-hardness —
- The computational hardness classification assigned here to distinguishing instances fitting in bins from those requiring more than bins.
Keywords : Bin packing · Configuration LP · Additive hardness
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Additive hardness and unbounded configuration gaps in bin packing
24/09/2026We 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.