Improved methods reduce space for packing dynamic square items
Improved Upper Bounds for Dynamic Bin Packing of General, Unit-Fraction, and Power-Fraction Squares
Data Structures and Algorithms
Summary
When you have square items that appear and disappear and need to fit them into boxes without moving them around too much, it’s tricky to do it efficiently. The authors found new ways to pack these squares so fewer boxes are needed at peak use. They focused only on rearranging items inside a box when new items arrive and proved tighter limits on how well certain packing methods can work. This makes dynamic packing better for general square sizes and special cases where the squares have sizes that are fractions or powers of fractions.
What this means in practice
- •For warehouse logistics teams: Optimize packing of varying sizes of square goods that arrive and depart dynamically with minimal repacking inside current storage units.
- •For cloud resource managers: Improve allocation of square-shaped resource blocks in real time with minimized migration, ensuring lower peak resource usage.
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.