We analyze the problem of packing squares in an online fashion: Given a semi-infinite strip of width 1 and an unknown sequence of squares of side length in [0,1] that arrive from above, one at a time. The objective is to pack these items as they arrive, minimizing the resulting height. Just like in the classical game of Tetris, each square must be moved along a collision-free path to its final destination. In addition, we account for gravity in both motion and position. We apply a geometric analysis to establish a competitive factor of 3.5 for the bottom-left heuristic and present a 34/13≈2.6154-competitive algorithm.
展开▼
