Online bin packing bounds tightened with exact computations and limits identified
Tightening the Online Bin Packing Gap from Both Sides, and the Limits of the Current Methods
Data Structures and Algorithms
Summary
Online bin packing is a problem where items must be packed into bins as they arrive, without knowing the future items. Since 2018, the best known performance of any online method was between two numbers: about 1.54 and 1.58. The authors improved the upper number slightly by recalculating it with exact math and exploring small adjustments to the algorithm. They also showed that the way the worst-case examples were built on the lower side can't be improved by extending known methods. This helps understand the limits of current approaches to online bin packing.
What this means in practice
- •For logistics planners: Improve real-time packing systems by using tighter performance bounds to evaluate algorithm options.
- •For cloud resource managers: Inform scheduling policies that allocate resources in an online manner with tighter guarantees on packing efficiency.
A theory result. No direct application yet.
Authors
Karyamsetty Martin
Abstract
The asymptotic competitive ratio of online bin packing has been bracketed since 2018 by the lower bound 1.54278 of Balogh, Bekesi, Dosa, Epstein and Levin and the upper bound 1.57829 of their Advanced Harmonic algorithm. We revisit both sides with exact rational computation and prove what the computations say. On the upper bound, we rebuild the certification of Advanced Harmonic as an exact optimization over its dual parameters; with the published parameters this already certifies a ratio strictly below the published one, and re-tuning the algorithm's proportion parameters gives a certified ratio of 1.5782147437 (an exact rational), independently re-verified on all 402 scenarios. To our knowledge this is the first movement of the upper bound since 2018. On the lower bound, we prove that the 2018 adversary construction is rigid: extending it by any finite number of new batches of ordinary size (outside the window of sizes s with 2s > 1 and rational part at most 0.64819), placed anywhere, with counts depending on the observed statistics, adaptive or not, never improves the bound at any truncation level. The load-bearing fact is that the construction is volume-tight at every stop. A single window-sized batch added to the truncation-3 tree is shown by machine-verified certificates to leave its value below the published limit. A computational map covers the remaining natural extensions: unions of structural variants, two-statistic multi-batch adversaries, and three families of adaptive conditions that the paper's separation theorem allows but never uses; none improves the bound. On the algorithm side we show that the marking, bonus-item and red-sand mechanisms of Extreme Harmonic bind nowhere in Advanced Harmonic, whose bottleneck is a two-medium-item bin that no known mechanism targets. We record two corrections to commonly cited numbers.