Math Conjectures

Modified integer round-up property for bin packing

OPENMajorConjectureProposed c. 1985 · Full conjecture

Canonical statement

Given item sizes a1,…,an∈(0,1]a_1,\ldots,a_n\in(0,1], let P={P⊆{1,…,n}:∑i∈Pai≤1}\mathcal P=\{P\subseteq\{1,\ldots,n\}:\sum_{i\in P}a_i\le1\}. Let OPT⁡\operatorname{OPT} be the minimum number of patterns from P\mathcal P, with repetitions allowed, whose incidence vectors sum coordinatewise to at least 1\mathbf1, and let
OPT⁡f=min⁡{∑P∈PxP:xP≥0, ∑P∋ixP≥1 (i=1,…,n)}. \operatorname{OPT}_f=\min\left\{\sum_{P\in\mathcal P}x_P:x_P\ge0,\ \sum_{P\ni i}x_P\ge1\ (i=1,\ldots,n)\right\}.
Then OPT⁡≤⌈OPT⁡f⌉+1\operatorname{OPT}\le\lceil\operatorname{OPT}_f\rceil+1.
View source LaTeX
Given item sizes \(a_1,\ldots,a_n\in(0,1]\), let \(\mathcal P=\{P\subseteq\{1,\ldots,n\}:\sum_{i\in P}a_i\le1\}\). Let \(\operatorname{OPT}\) be the minimum number of patterns from \(\mathcal P\), with repetitions allowed, whose incidence vectors sum coordinatewise to at least \(\mathbf1\), and let
\[
\operatorname{OPT}_f=\min\left\{\sum_{P\in\mathcal P}x_P:x_P\ge0,\ \sum_{P\ni i}x_P\ge1\ (i=1,\ldots,n)\right\}.
\]
Then \(\operatorname{OPT}\le\lceil\operatorname{OPT}_f\rceil+1\).
OR-004:[ScheithauerTerno1995MIRUP][KarmarkarKarp1982BinPacking][HobergRothvoss2017BinPacking]
Operations researchMathematical optimization

Notes

In one-dimensional bin packing, equivalently the cutting stock problem, OPT⁡\operatorname{OPT} is the minimum number of unit bins needed and OPT⁡f\operatorname{OPT}_f is the optimum of the pattern-based linear programming relaxation. The modified integer round-up property conjecture asserts that OPT⁡≤⌈OPT⁡f⌉+1\operatorname{OPT}\le\lceil\operatorname{OPT}_f\rceil+1: one never needs more than a single bin beyond the rounded-up fractional optimum. The modified form crystallized in the mid-1980s, after counterexamples ruled out the plain round-up property OPT⁡≤⌈OPT⁡f⌉\operatorname{OPT}\le\lceil\operatorname{OPT}_f\rceil, and was studied in this shape by Scheithauer and Terno [ScheithauerTerno1995MIRUP].

The known additive gaps are remarkably small. Karmarkar and Karp gave a polynomial-time rounding scheme with polylogarithmic additive error [KarmarkarKarp1982BinPacking], and Hoberg and Rothvoss sharpened the integrality gap to O(log⁡OPT⁡f)O(\log\operatorname{OPT}_f) [HobergRothvoss2017BinPacking]. In the other direction, no family of instances with an unbounded additive gap has ever been found.

The conjecture is open: a proof must replace the logarithmic additive term by the absolute constant 11, while a refutation would require an instance whose gap above ⌈OPT⁡f⌉\lceil\operatorname{OPT}_f\rceil is at least 22.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.