HEXAGONbeta

Additive Rounding for LP-Tight Three-Item Bin Packing

Primarily human-written textHuman understanding: all partsmath.OC — Optimization and Controlmath.CO — Combinatoricscs.DS — Data Structures and Algorithms

Contributed by Ruixue Yuan ↗, Da Teng ↗, Zhenyu Sun ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

We consider bin-packing instances with 3m3m items of sizes in (1/4,1/2)(1/4,1/2), total size mm, and configuration linear programming value mm. Let dd be the relative dimension of the polytope of zero-sum multiplicity patterns obtained by centering sizes at 1/31/3. We determine the maximum additive integrality gap for every d≤10d\le10. It is zero for d≤4d\le4 and one for 5≤d≤105\le d\le10. More generally, a representation of the multiplicity vector by at most five zero-sum patterns admits an integral packing, and a representation by at most eleven patterns requires at most one additional bin. The integral-packing result has a structural proof; the additive-one result combines structural restrictions with exact finite enumeration. For arbitrary dd, we construct an LP-tight subinstance with at most 6d+36d+3 items and no smaller additive gap. An integer representation preserving the signs of triple sums then yields a finite rational family attaining the worst gap, which is computable in time 2O((d+1)2)2^{O((d+1)^2)}. Finally, we construct a sharp family with simplex pattern polytopes and a linearly growing zero-sum matching deficit. Its eleven-dimensional member violates the zero-sum remainder condition used in the ten-dimensional proof. Thus the bound of eleven fractional patterns in that condition is sharp.

References

  1. Caprara, Alberto; Dell'Amico, Mauro; Díaz-Díaz, José Carlos; Iori, Manuel; Rizzi, Romeo. Friendly Bin Packing Instances without Integer Round-up Property. Mathematical Programming, vol. 150, no. 1, pp. 5–17. 2015DOI
  2. Eisenbrand, Friedrich; Pálvölgyi, Dömötör; Rothvoß, Thomas. Bin Packing via Discrepancy of Permutations. ACM Transactions on Algorithms, vol. 9, no. 3, pp. 24:1–24:15. 2013DOI
  3. Füredi, Zoltán. Maximum Degree and Fractional Matchings in Uniform Hypergraphs. Combinatorica, vol. 1, no. 2, pp. 155–162. 1981DOI
  4. Gilmore, Paul C.; Gomory, Ralph E. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, vol. 9, no. 6, pp. 849–859. 1961DOI
  5. Goemans, Michel X.; Rothvoß, Thomas. Polynomiality for Bin Packing with a Constant Number of Item Types. Journal of the ACM, vol. 67, no. 6, pp. 38:1–38:21. 2020
  6. Hoberg, Rebecca; Rothvoß, Thomas. A Logarithmic Additive Integrality Gap for Bin Packing. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2616–2625. 2017DOI
  7. Karmarkar, Narendra; Karp, Richard M. An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pp. 312–320. 1982DOI
  8. Rietz, Jürgen; Scheithauer, Guntram; Terno, Johannes. Families of Non-IRUP Instances of the One-Dimensional Cutting Stock Problem. Discrete Applied Mathematics, vol. 121, no. 1–3, pp. 229–245. 2002
  9. Rothvoß, Thomas. Approximating Bin Packing within O(log⁡OPT⋅log⁡log⁡OPT)O(\log\mathrm{OPT}\cdot\log\log\mathrm{OPT}) Bins. Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 20–29. 2013DOI
  10. Turán, Pál. Egy gráfelméleti szélsőértékfeladatról. Matematikai és Fizikai Lapok, vol. 48, pp. 436–452. 1941

Version history

  1. v1Submitted by Zhenyu SunInitial depositCurrentOct 19, 2026