Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.
OAI-26 family 118: unbounded configuration-LP gaps for bin packing
Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This article reports source-pinned publisher claims and does not independently verify the asserted counterexamples or hardness reductions.
The question in plain language
Bin packing asks how to place items of specified sizes into as few unit-capacity bins as possible. A mathematical relaxation allows fractional combinations of feasible bin contents, which can be easier to optimize than a genuine packing. The integrality gap measures the difference between the best actual packing and the fractional optimum.
Family 118 claims that this additive difference can become arbitrarily large for the standard configuration linear program, and that finding a packing within any fixed additive number of optimal bins is NP-hard.
A small example
Suppose items have sizes \(0.4,0.4,0.4\). A real packing needs two unit bins: two items fit together, while all three do not. A configuration represents a collection of items that could share one bin without exceeding capacity. The configuration LP permits nonnegative fractional weights on such configurations, subject to covering the items.
These fractional weights are not literal fractions of physical bins. Rounding them to whole bins may require extra bins. The disputed modified integer round-up conjecture concerns whether a universal constant controls that extra number.
What is known
The protected Family 118 catalogue lists one manuscript, Additive hardness and unbounded configuration gaps in bin packing.
The pinned publisher overview claims that the integer optimum \(\mathrm{OPT}(I)\) and the configuration LP optimum \(\mathrm{LP}(I)\) satisfy unbounded additive separation: for every constant \(C\) there are bin-packing instances \(I\) with
This is an additive claim, not the assertion of an unbounded multiplicative ratio. The overview presents the result as a counterexample to the modified integer round-up conjecture of Scheithauer and Terno.
Separately, the overview claims that, for every fixed additive constant, approximating the integral optimum within that many bins is NP-hard, even if each item is larger than \(1/6\). Under this promise, every bin can accommodate at most five items because six such items would sum to more than one. The hardness statement and the LP-gap counterexample must not be conflated without checking the reduction and instance-family hypotheses.
GCL verification state
Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The protected catalogue identifies one PDF; the pinned overview attributes the unbounded additive gap and fixed-additive-approximation hardness claims to it.
This documentary pass has not independently verified the LP formulation, the exact rounded-up conjecture statement, the family of gap instances, or the NP-hardness proof. No Family 118-specific Lean elaboration, Comparator receipt, critical mathematical audit, or MATHCERT certification is asserted.
What remains
Read the pinned manuscript and reconstruct the configuration LP, including multiplicities, item identities, capacity convention, feasible configurations, and whether the LP optimum is attained. Identify the precise modified integer round-up conjecture and whether its formulation involves a ceiling operation, which must be addressed when translating unbounded gaps.
Audit the constructive or existential gap family and obtain independently checkable LP bounds and integer lower bounds. For additive approximation hardness, extract the decision promise, reduction from an established NP-hard problem, encoding of rational item sizes, and quantifier order for the fixed constant. Verify the strict \(1/6\) threshold and the implied five-item capacity restriction.
Complete mathematical Markdown and MkDocs regression, source-critical editorial review, and protected merge/readback. Editorial admission would not constitute proof certification.
Sources and claim boundaries
Boundary: NO_CERTIFICATION. Both the integrality-gap and additive-hardness claims await independent mathematical verification.
Indexed primary manuscript paths:
- Additive hardness and unbounded configuration gaps in bin packing —
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