Discoveries / algorithms-optimization

Source authenticated

The Modified Integer Round-Up Conjecture for bin packing (Scheithauer-Terno)

Theorem 1.1: for every integer $c\ge0$ there are a finite rational instance $I$ , every item larger than $1/6$ (so at most five items per bin), and an integer $B$ with $LP(I)=B$ and $OPT(I)>B+c$ ; the same LP value holds for the stronger formulation whose patterns are subsets of individual item copies. So the additive integrality gap of the configuration LP is unbounded and the Modified Integer Round-Up Conjecture is false. Not shown: a gap growing like $\log OPT$ in the instance size, matching the Hoberg-Rothvoss upper bound; the paper says it obtains no such lower bound.

Exact FrontierDelta

Prior state unknown→disproved

Scope and record

Occurred: Sep 24, 2026

Delta type: SOURCE CLAIM

Assumptions: VibeMathed verification: lean-checked. Publication: announcement. AI contribution: ai-discovered. VibeMathed editorial classifications, scores, notes, relations, and dataset structure are CC BY 4.0. Source statements and linked content retain their own rights.

Canonical aliases: The Modified Integer Round-Up Conjecture for bin packing (Scheithauer-Terno) · Modified integer round-up conjecture

Confidence: Not scored

Registry verification: lean checked · announcement · candidate

Open the source record ↗

Attribution

VibeMathed
registry · event recorded by

Unreleased internal OpenAI model
model · ai model contributor · OpenAI

Evidence vector

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Named evidence

VibeMathed record: The Modified Integer Round-Up Conjecture for bin packing (Scheithauer-Terno)

specialist registry · passed

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the conjecture: for every $c\ge0$ it gives a rational instance with all sizes above $1/6$ , integral $LP(I)=B$ and $OPT(I)>B+c$ ; taking $c=1$ contradicts the conjecture with no ceiling ambiguity. Lean: formalization.yaml lists comparator ComparatorChallenges/BinPackingGap.json, declaration OAI.BinPackingGap.main_results in OAI/Computability/BinPacking/Main.lean. The statement was read here: its first conjunct says that for every $c$ there are an instance with $5B$ items, sizes in $(1/6,1)$ , $B+c<opt$ , and both the individual-copy and the size-type configuration LP values equal to $B$ , the LPs being infima of fractional covers. That states the headline. Not rebuilt here. The instances come from a vertex-cover reduction and grow very fast with $c$ .

Source ↗

OpenAI, Additive hardness and unbounded configuration gaps in bin packing (source theorem)

paper · pending

Primary source named by the VibeMathed record. Presence in this import is not an independent mathematical verification.

Source ↗

Lean proof: OAI/Computability/BinPacking/Main.lean

lean artifact · pending

lean-proof link supplied by the VibeMathed registry.

Source ↗

Lean statement: ComparatorChallenges/BinPackingGap.lean

lean artifact · pending

lean-proof link supplied by the VibeMathed registry.

Source ↗

Scheithauer and Terno, The modified integer round-up property of the one-dimensional cutting stock problem (1995)

specialist registry · pending

problem-record link supplied by the VibeMathed registry.

Source ↗

Artifacts and verifiers

Lean proof: OAI/Computability/BinPacking/Main.lean

lean artifact · pending

Artifact ↗

Lean statement: ComparatorChallenges/BinPackingGap.lean

lean artifact · pending

Artifact ↗

Compute record

No linked compute attempts recorded.

Lineage and corrections

Lean statement: ComparatorChallenges/BinPackingGap.lean evidence for this event

VibeMathed record: The Modified Integer Round-Up Conjecture for bin packing (Scheithauer-Terno) evidence for this event

This event attributed to Unreleased internal OpenAI model

Lean proof: OAI/Computability/BinPacking/Main.lean evidence for this event

Scheithauer and Terno, The modified integer round-up property of the one-dimensional cutting stock problem (1995) evidence for this event

The Modified Integer Round-Up Conjecture for bin packing (Scheithauer-Terno) parent of this event

OpenAI, Additive hardness and unbounded configuration gaps in bin packing (source theorem) evidence for this event

Act on this frontier

Verify, challenge, or extend the result.

Help verify Open canonical problem Explore evidence graph