Bin packing: additive error and configuration gaps

Source and verification

This article explains family 118 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Bin patterns and fractional packings

An instance $I$ is an explicit list of rational item sizes $a_i\in (0,1]$, encoded in binary. A bin holds items of total size at most one. The optimum $\mathrm{OPT}(I)$ is the smallest number of bins covering all copies.

A configuration records a feasible bin pattern. There are two useful linear relaxations. In the numerical-type formulation, distinct sizes form a set $\mathcal{S}$, with demand $n_{\sigma }$ for size $\sigma$. A pattern is a nonnegative integer vector $c$ satisfying ${\sum }_{\sigma }\sigma c_{\sigma }\le 1$. Assigning it weight $z_c$ gives

$$\begin{array}{c}\mathrm{LP}(I)=\min \sum _c{z}_c,\\ \sum _c{c}_{\sigma }{z}_c\ge n_{\sigma },z_c\ge 0.\end{array}$$

These patterns may repeat a size more often than it occurs in the input. Capacity, rather than availability, bounds each pattern’s multiplicities.

The individual-copy formulation instead indexes every physical item separately. A pattern $H$ is a subset of available copies with ${\sum }_{i\in H}{a}_i\le 1$. Its weight $y_H$ must satisfy ${\sum }_{H\ni i}{y}_H\ge 1$ for each item, and the objective is ${\sum }_H{y}_H$. Write its optimum as ${\mathrm{LP}}_{\mathrm{ind}}(I)$.

Projecting an individual-copy solution to numerical types gives

$$\mathrm{LP}(I)\le {\mathrm{LP}}_{\mathrm{ind}}(I)\le \mathrm{OPT}(I).$$

For three items of size $1/2$, each pair is a feasible individual-copy pattern. Weight $1/2$ on each of the three pairs covers every item once and costs $3/2$, whereas two integral bins are needed. This illustrates fractional splitting, but only gives the elementary rounding gap. The manuscript constructs gaps exceeding every fixed additive allowance.

🏷️ Structural gaps and algorithmic hardness

Manuscript statements

For every integer $c\ge 0$, there is a rational instance of $5B$ items, all strictly larger than $1/6$, such that

$$\begin{array}{c}\mathrm{LP}(I)={\mathrm{LP}}_{\mathrm{ind}}(I)=B,\\ \mathrm{OPT}(I)>B+c.\end{array}$$

Separately, for every fixed $c$, distinguishing instances packable in $B$ bins from those not packable in $B+c$ bins is NP-hard, with $B$ supplied as an integer. (OpenAI, 2026)

The structural claim is unconditional within the manuscript’s proof. Taking $c=1$ contradicts the Modified Integer Round-Up Conjecture

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

The LP value in the construction is integral, so the ceiling cannot absorb the excess.

The algorithmic claim says that a deterministic polynomial-time algorithm with one absolute additive allowance exists exactly when $P=NP$. This is distinct from disproving an existential LP bound. It also differs from a $(1+\epsilon )$ asymptotic ratio, whose permitted additive excess grows like $\epsilon \mathrm{OPT}$.

Items larger than $1/6$ force at most five items per bin. They do not bound the number of distinct sizes or the binary precision of those sizes. The manuscript does not claim a matching logarithmic lower bound as a function of the input length; the instances may grow very rapidly with $c$.

🏷️ A reduction that controls arbitrary packings

The common construction starts with a graph on $n$ vertices and a vertex-cover target $k$. A vertex cover meets every edge. For fixed $c\ge 0$ and $\rho >0$, the source produces $5B$ items with the following interface:

• A cover of size at most $k$ yields a packing into $B$ bins.
• Any packing into at most $B+c$ bins yields a cover of size at most $k+\rho n$.

The encoding length and construction time are polynomial for each fixed pair $(c,\rho )$. The second implication must apply to every feasible packing, including bins absent from the displayed fractional solution. An obstruction to rounding only one chosen fractional support would not establish a gap for the full configuration LP.

The reduction’s local resource system uses two finite rooted trees. At each depth there is a quota of marked vertices. Each tree individually has a marking meeting every root-to-leaf path at least $d$ times within those quotas. Sharing the same quotas across both trees prevents both trees from having even one mark on every path. The construction places these alternatives in plus and minus interval regions for each graph vertex. Almost $d$ global resources must therefore supplement one side; the plus-side expenditure determines the extracted cover.

🏷️ Prefix counts turn bins into interval coverage

An intended bin has five roles: a row, an anchor, a global auxiliary, a local auxiliary, and a flag. In a deadline bin, a row starts at a baseline $b$, auxiliary lengths move it to a completion location $h\le b$, and the anchor supplies a deadline $z$. Feasibility expresses $h\le z$.

The elementary identity is

$$1_{h\le t}-1_{b\le t}=1_{[h,b)}(t).$$

Thus changing rows from baseline locations to completion locations increases the prefix count at $t$ exactly by the number of their intervals covering $t$. Moving $d$ deadlines from the right end of a test interval to its left end forces at least $d$ additional completions throughout that interval. A scalar packing condition has become a geometric coverage requirement.

Local resources can cover at most one cell at the appropriate depth, and their counts enforce the tree quotas. Global resources pay for the side where local quotas are insufficient. The interval formulation makes this accounting hold simultaneously over the many tests belonging to one vertex.

🏷️ Edge permits and conservation

A second bin type pairs a job row with a key. Each graph edge creates repeated jobs at both endpoints. A long job paired with the key at its own position must consume a permit assigned to that edge, or a resource belonging to an earlier edge.

The numerical order prevents borrowing from later rows or later edges. Borrowing an earlier row creates a prefix deficit in the deadline bins. That deficit forces compensating interval coverage. Consequently, if a vertex’s plus allocation is small, many long jobs must be matched at their exact positions. Conservation bounds how many can be paid with earlier-edge resources. If both endpoints of an edge have small plus allocation, its permit supply is insufficient. Every edge therefore has a sufficiently funded endpoint.

The source encodes all these coordinates into ordinary scalar sizes near $1/5$. Several integer scores classify five-item bins and order their labels. Conservation bounds the exceptional items and unequal-label matches. A key quantitative feature is that the error charged at a vertex is independent of its number of job positions. Otherwise repeating tests would enlarge the soundness error along with the desired amplification. (OpenAI, 2026)

One simple part of this stability can already be seen from cardinality. A packing of $5B$ items into at most $B+c$ bins has at most $5c$ unused item slots relative to five per bin. Hence the number of bins containing fewer than five items is at most $5c$. This alone does not classify the five-item bins: the source’s score conservation is needed to control their possible role and label patterns.

🏷️ An exact fractional witness and a four-vertex obstruction

Because every bin contains at most five items, assigning dual weight $1/5$ to each of the $5B$ physical items proves ${\mathrm{LP}}_{\mathrm{ind}}\ge B$. The same cardinality bound gives $\mathrm{LP}\ge B$: assign type weight $1/5$ and pair it with the item multiplicities.

For the upper bound, use the complete graph $K_4$ with target $k=2$. The construction gives every vertex two local states. Mix them with weights $1/2$ and $1/2$. Each state uses the appropriate labeled items once, and averaged resource demands match the global inventories. The source explicitly distributes this mixture over physical copies, rather than assuming that a type-level solution automatically lifts to the stronger relaxation. Its total weight is $B$.

The minimum vertex cover of $K_4$ has size three: omitting any two vertices leaves their connecting edge uncovered. Set $\rho =1/8$. A hypothetical packing into $B+c$ bins would extract a cover of size at most

$$k+\rho n=2+\frac{1}{8}\cdot 4=\frac{5}{2}<3,$$

a contradiction. This deduction uses only the finite construction and its soundness, not a complexity assumption. The fractional mixture is valid even though its local states cannot be realized together as an integral packing.

🏷️ From satisfiability gaps to additive hardness

For the algorithmic consequence, the source starts with a fixed satisfiability gap: all clauses are satisfiable in the YES case, while at most $(1-\eta )M$ of $M$ clauses can be satisfied in the NO case.

Create one vertex for each of three literal slots per clause. Join each clause’s slots into a triangle and join complementary literal slots. An independent set picks at most one consistent literal per clause, so its maximum size equals the maximum number of simultaneously satisfiable clauses. Therefore

$$\begin{array}{c}n=3M,k=2M,\\ \tau (G)=3M-\mathrm{MAXSAT},\end{array}$$

where $\tau (G)$ is the minimum cover size. The NO case has $\tau (G)\ge k+(\eta /3)n$. Choosing $\rho <\eta /3$ makes a $B+c$ packing contradict this lower bound, while a satisfying assignment gives a $B$ packing.

If an algorithm always outputs at most $\mathrm{OPT}+C$ bins, take a fixed integer $c\ge C$. Its output distinguishes this promise gap, implying $P=NP$. Conversely, under $P=NP$, exact rational bin feasibility is decidable in polynomial time. Binary search finds the optimum number of bins; successively fixing each item’s bin and testing whether a completion exists constructs an optimal packing. This supplies the search direction of the equivalence as well as the decision direction.

🏷️ Key steps and proof outlines

Prefix conservation gives coverage at every test point

Fix an arbitrary packing into at most $B+c$ bins. The classification lemmas first show that all but a controlled number of anchors participate in good five-role tuples. In “Extracting a small vertex cover,” let $K$ denote the resulting error budget per label, and let $d$ be the amplification parameter. For a graph vertex $v$, let $B_v(a)$ count the intended row baselines at most $a$, $A_v(a)$ the baselines of actual good deadline tuples, and $C_v(a)$ their completion locations at most $a$. (OpenAI, 2026)

Inside a test interval, moving deadlines left creates exactly $d$ additional deadlines in the prefix. At most $3K$ anchors are bad, so good matching implies

$$C_v(a)\ge B_v(a)+d-3K.$$

On the other hand, earlier keys consume their own required number of earlier rows. At most $3K$ deviations can free additional rows for deadline tuples, giving $A_v(a)\le B_v(a)+3K$. Subtracting and using the interval identity yields

$$I_v(a)=C_v(a)-A_v(a)\ge d-6K.$$

This argument holds at every test point, including tied endpoints because intervals are half-open. The original baseline prefix need not equal the prefix used by the candidate packing; the two inequalities are precisely what controls that discrepancy.

Competing trees force one expensive side

A global interval reaches only its designated plus or minus region. A tuple with a positive local length can meet at most one cell at its depth, by the geometric separation of cells. Mark that cell in its tree. The local item inventory bounds the total marks at each depth across both trees.

Suppose both global allocations $x_v^{+}$ and $x_v^{-}$ were smaller than $d-6K$. Since every leaf test point needs at least $d-6K$ covering intervals, at least one local interval would have to cover each leaf in both trees. The induced marks would hit every root-to-leaf path in both trees while respecting their shared depth quotas. This contradicts the competing-tree lemma. Therefore

$$x_v^{+}\ge d-6K\text{or}{x}_v^{-}\ge d-6K.$$

The lemma forces a side for every vertex, but does not yet force a vertex cover. The next accounting step links the chosen sides to graph edges.

Displaced rows strengthen, rather than evade, the test

Consider a job position whose cell is not touched by a positive local interval. Let $\xi$ count keys there matched to earlier rows. Those rows are then unavailable for earlier deadline tuples, improving the baseline estimate to $A_v(a)\le B_v(a)+3K-\xi$ at an interior point of the job cell. The required interval coverage consequently increases by $\xi$.

At this point coverage can come only from global plus intervals or short rows of the current position. Comparing available short rows with the number of keys still needing long rows yields the source’s bound

$$L_{v,r}\ge d-x_v^{+}-9K,$$

where $L_{v,r}$ counts good long matches at their exact job position. Borrowing earlier rows therefore does not defeat the extraction: the prefix deficit forces compensating long matches. Only a bounded number of positions are excluded by local intervals, independent of the total number of repeated jobs.

Conservation of edge permits then shows that both endpoints of an edge cannot have small plus allocations. The funded-plus vertices form a cover. Their number is bounded using ${\sum }_v{x}_v^{+}\le dk$, with amplification chosen so the accumulated classification errors add at most $\rho n$.

Why the fractional witness does not contradict extraction

In the $K_4$ example, the fractional solution mixes the two local states of each vertex equally. Linear resource constraints see only the averages and are satisfied at cost $B$. An integral packing must choose actual simultaneous tuples and is subject to the prefix and permit conservation just proved. It would extract a cover of size at most $5/2$, whereas every cover of $K_4$ has size at least three. Thus the contradiction uses the soundness theorem for all packings, not merely failure to round the particular displayed fractional support.

See Also

• Uniform sparsest cut separates a relaxation obstruction from a computational reduction in another optimization problem.
• Common-base counting explains why labeled copies and occupancy types can have different multiplicities; here the two configuration formulations likewise require separate witnesses.

🏷️ Manuscripts and verification scope

• Additive hardness and unbounded configuration gaps in bin packing — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope includes both configuration formulations, the unconditional unbounded gaps, and the fixed-additive hardness and complexity equivalence. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Additive hardness and unbounded configuration gaps in bin packing.