Improved methods reduce worst case for packing squares dynamically
Improved Upper Bounds for Dynamic Bin Packing of General, Unit-Fraction, and Power-Fraction Squares
Data Structures and Algorithms
Summary
Packing squares into bins efficiently is a tricky problem that becomes even harder when squares arrive and leave over time. This paper shows better strategies to keep the number of bins used as low as possible while only moving squares within the same bin when adding new ones. The authors developed a simpler algorithm and proved tighter limits, lowering the worst-case efficiency ratio for general squares and for special cases like unit-fraction and power-fraction square sizes. Their work breaks previous theoretical limits and improves how well we can pack squares in changing conditions.
bin packingdynamic algorithmsasymptotic competitive ratioNext-Fit Decreasing Heightsquare packingunit-fraction squarespower-fraction squaresrepackingalgorithm upper bounds
Authors
Miguel A. Mini, Flávio K. Miyazawa, Gabriel M. Silva, Yoshiko Wakabayashi
Abstract
This paper presents significant upper-bound improvements for dynamic 2D square bin packing, where square items arrive and depart over time and the objective is to minimize the peak number of concurrent active unit bins. In our model, repacking is permitted only within a destination bin upon item arrival; migration between active bins is strictly forbidden. By introducing a streamlined two-list algorithm and proving a tight $5/16$ occupied-area bound for Next-Fit Decreasing Height, we reduce the upper bound on the asymptotic competitive ratio for arbitrary squares from 4.2154 down to 3.918, breaking a longstanding theoretical ceiling. For restricted variants, we establish asymptotic competitive ratios of at most 3.356 for unit-fraction side lengths and 2.211 for power-fraction side lengths.