Unbounded bin-packing gaps and the modified integer round-up conjecture

← All digests

Family 118 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-09

Bin packing asks how many unit-capacity containers are needed for a collection of items. A powerful linear relaxation permits fractional numbers of feasible bin patterns, often giving a remarkably accurate lower bound. Family 118 claims that the discrepancy between this fractional value and a real packing is nevertheless unbounded, and that no fixed additive approximation allowance is efficiently attainable unless P equals NP.

1. The question

Each item has a rational size between zero and one. Items must be assigned whole to bins, with total size at most one in each bin. The objective is to minimize the number of bins.

Suppose a fractional optimization method says that one hundred bins should suffice. Must a genuine packing fit into one hundred and one? Or can an unavoidable extra cost grow beyond every fixed number of bins?

The modified integer round-up conjecture predicted a very small discrepancy: round the fractional optimum up to an integer, then allow one additional bin. The manuscript claims counterexamples with arbitrarily large additive gaps.

A related but distinct question asks whether an algorithm can always construct a packing using at most a fixed number of bins beyond the true optimum. The same paper claims hardness for every such fixed allowance.

2. Background and essential definitions

Integral packings and configurations

Write $\operatorname{OPT}(I)$ for the minimum number of bins for an instance $I$. A configuration is any collection of item sizes whose total is at most one: it describes one feasible bin pattern.

If $S$ is the set of distinct numerical sizes and $n_\sigma$ is the number of items of size $\sigma$, a type configuration is an integer vector $c=(c_\sigma)$ satisfying

$$\sum_{\sigma\in S}\sigma c_\sigma\le1.$$

The configuration linear program chooses nonnegative real weights $z_c$, interpreted as fractional numbers of bins of each pattern, and minimizes

$$\operatorname{OPT}_{\mathrm{LP}}(I) =\min\left\{\sum_c z_c: \sum_c c_\sigma z_c\ge n_\sigma\text{ for every }\sigma\right\}.$$

Every real packing gives a feasible integral choice of pattern weights. Hence the fractional optimum is a lower bound on the packing optimum.

Two pattern conventions

The ordinary type formulation may repeat a size within a pattern as often as capacity allows, even beyond its available input multiplicity. An individual-copy formulation instead gives every physical item a distinct identity and permits a pattern to use each at most once.

These formulations can differ. The manuscript states its main notation for the ordinary numerical-type version and separately establishes the same gap for the stronger individual-copy version on its constructed instances.

Additive and multiplicative errors

A multiplicative guarantee uses at most $(1+\varepsilon)\operatorname{OPT}$ bins, perhaps with an additional term. Its excess can grow as the optimum grows. At optimum one million, even one-percent error permits ten thousand extra bins.

An additive guarantee uses at most $\operatorname{OPT}+C$ bins, where $C$ is fixed independently of input size. That is a much sharper requirement for large instances.

The modified integer round-up conjecture is the structural assertion

$$\operatorname{OPT}(I)\le\lceil\operatorname{OPT}_{\mathrm{LP}}(I)\rceil+1.$$

It predicts existence of a near-fractional packing. It does not itself supply an efficient algorithm to find one.

3. Development history and previous partial results

Configuration methods grew out of cutting-stock optimization. Gilmore and Gomory’s 1961 formulation uses linear programming over feasible cutting patterns, with column generation to avoid listing every pattern initially.

The stronger integer round-up property, which would need no extra bin after rounding, was studied by Marcotte and disproved by explicit instances. Scheithauer and Terno investigated the modified one-extra-bin proposal, followed by further theoretical work.

On the algorithmic side, Fernandez de la Vega and Lueker obtained an asymptotic approximation scheme: for fixed accuracy, the multiplicative ratio approaches one on sufficiently large optima. That still permits an unbounded additive discrepancy.

Karmarkar and Karp combined grouping with configuration-LP methods to obtain a logarithmic-squared additive bound. Discrepancy-based rounding later improved this to order $\log\operatorname{OPT}\,\log\log\operatorname{OPT}$, and Hoberg and Rothvoss achieved logarithmic additive loss.

Earlier discrepancy constructions showed that algorithms confined to rounding the support of a particular fractional solution could need many extra bins. But an unrestricted integral packing can use other configurations. A lower bound for one rounding method therefore does not by itself prove a gap for the full configuration LP.

This distinction motivates the new manuscript’s extraction argument: it must analyze every sufficiently small packing, including those using unintended combinations of items.

4. What the new manuscripts claim

For every integer $c\ge0$, M1 claims a finite rational bin-packing instance and an integer $B$ such that

$$\operatorname{OPT}_{\mathrm{LP}}(I)=B, \qquad \operatorname{OPT}(I)>B+c.$$

The same fractional value is obtained in the individual-copy formulation. Because $B$ is already integral, the gap cannot be explained by ambiguity about taking a ceiling.

Every item is strictly larger than $1/6$. Consequently each bin contains at most five items. Unbounded additive gaps therefore occur even under this fixed bound on the number of items in a bin.

Taking $c=1$ contradicts the modified integer round-up conjecture. The stronger statement is that no absolute additive upper bound holds for these configuration relaxations.

Separately, for every fixed $c$, the paper claims NP-hardness of distinguishing instances packable in $B$ bins from instances not packable in $B+c$ bins, again with all sizes larger than $1/6$.

It follows that a deterministic polynomial-time algorithm with any fixed additive guarantee exists if and only if $\mathsf P=\mathsf{NP}$. The structural gap theorem itself has no complexity-class assumption; the algorithmic impossibility conclusion uses the usual separation assumption.

5. Why the advance matters

Importance: 3/5, provisional. The claim would settle a longstanding question about a central relaxation in packing and cutting stock, while locating a genuine barrier to constant-additive approximation.

The result changes how the fractional bound can be interpreted. It remains a valid lower bound and can remain very accurate on many instances, but it cannot support a universal promise of only one or a few additional bins.

The restriction to at most five items per bin is striking because it eliminates explanations based solely on bins containing huge numbers of tiny objects. The obstruction instead comes from how many locally feasible patterns interact globally.

The claim does not invalidate asymptotic approximation schemes or logarithmic additive upper bounds. An unbounded gap may grow slowly with instance size and remain a vanishing fraction of the total optimum.

6. The main idea

Encode a graph-cover decision in packing

The manuscript reduces from vertex cover. A vertex cover is a set of graph vertices containing at least one endpoint of every edge.

For a fixed additive allowance and a small accuracy parameter, the construction creates items with two local states for each graph vertex. Choosing the appropriate state corresponds to placing that vertex in a cover. Edge-related resources enforce that each edge has a sufficiently funded endpoint.

A small vertex cover gives an intended packing into $B$ bins. Conversely, any packing into only $B+c$ bins can be decoded into a vertex cover of controlled size. The converse is what makes the reduction useful for hardness.

Competing interval requirements force choices

Inside each vertex gadget, two rooted trees organize nested intervals and resource quotas. Each tree separately can satisfy a demanding path-coverage requirement. When both compete for the same quotas, they cannot simultaneously satisfy even a weaker requirement everywhere.

This forces additional global resources onto one side of the gadget. The selected side records the vertex-cover choice. Tests corresponding to graph edges are placed near the relevant intervals so that incompatible local choices cannot all be accommodated with the available resources.

The trees and intervals are analytical components of a numerical construction. The final instance is ordinary one-dimensional bin packing, with rational scalar item sizes.

Use five item roles near one fifth

An intended bin combines five roles: a row item, an anchor, two kinds of auxiliary resource, and a flag. Small perturbations of sizes near one fifth encode labels, ordering constraints, and interval endpoints.

Because all sizes exceed one sixth, no bin can contain six items. Carefully separated numerical coordinates ensure that a five-item bin fits only when the encoded conditions cooperate.

For example, an anchor can act like a deadline while auxiliary lengths determine a completion coordinate. Feasibility of that bin becomes an inequality comparing completion with deadline. Prefix counts of such inequalities translate into interval-coverage requirements.

Control unintended packings

An arbitrary packing is free to mix roles and labels. The paper assigns integer scores to items and uses conservation of total scores to show that a packing with only a fixed number of extra bins has only a bounded number of serious deviations from the intended patterns.

A second ordering argument controls mismatched labels. The error at a vertex is bounded independently of the number of internal positions in its gadget, allowing the coverage tests to retain their force.

For the structural LP gap, the paper uses a small graph and fractional mixtures of the two local states. Each local state uses its labeled items consistently, while averaging balances global inventories. A distribution over physical copies yields the fractional solution of value $B$, and the five-item bound supplies a matching lower bound on that value.

The fractional mixture can combine locally valid choices that no equally economical integral packing can realize simultaneously. This is the source of the gap.

7. Scope, limitations, and open questions

The unbounded-gap theorem does not establish a matching logarithmic lower bound in terms of item count or optimum. The constructed instances can grow very rapidly as the prescribed gap increases.

A fixed maximum number of items per bin is different from a fixed number of distinct sizes. The construction may use many numerical sizes. Goemans and Rothvoss give polynomial-time solvability when the number of item types is fixed, a different parameter regime.

The hardness result concerns worst-case inputs and fixed additive allowances. It does not rule out useful heuristics, exact algorithms for small instances, or stronger guarantees under additional structure.

The next quantitative question is how the largest possible full-LP gap grows with instance size, beyond merely being unbounded.

8. Sources and further reading

M1’s Definitions 1.1 and Theorems 1.2–1.3 distinguish the two LP formulations, the unconditional structural gap, and the hardness reduction. The historical cutting-stock and approximation papers linked above explain why none of these statements is equivalent to the existence of a good multiplicative approximation scheme.

Source manuscripts

• M1. OpenAI, Additive hardness and unbounded configuration gaps in bin packing (September 24, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.