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 (squares must never move up) and position (any final destination must be supported from below). A similar problem has been considered before; the best previous result is by Azar and Epstein, who gave a 4-competitive algorithm in a setting without gravity (i.e., with the possibility of letting squares "hang in the air") based on ideas of shelf-packing: Squares are assigned to different horizontal levels, allowing an analysis that is reminiscent of some bin-packing arguments. We apply a geometric analysis to establish a competitive factor of 3.5 for the bottom-left heuristic and present a 34 13=2.615...-competitive algorithm.
For the case in which rotation is possible, they present a 4-competitive strategy based on shelf-packing methods: Each rectangle is rotated such that its narrow side is the bottom side. The algorithm tries to maintain a corridor at the right side of the strip to move the rectangles to their shelves. If a shelf is full or the path to it is blocked, by a large item, a new shelf is opened. Until now, this is also the best deterministic upper bound for squares. Note that in this strategy gravity is not taken into account as items are allowed to be placed at appropriate levels. Coffman @cite_1 consider probabilistic aspects of online rectangle packing without rotation and with Tetris constraint. If @math rectangle side lengths are chosen uniformly at random from the interval @math , they show that there is a lower bound of @math on the expected height for any algorithm. Moreover, they propose an algorithm that achieves an asymptotic expected height of @math .
@cite_1
2012437618
Rectangles with dimensions independently chosen from a uniform distribution on [0, 1] are packed on-line into a unit width strip under a constraint like that of the Tetris game: rectangles arrive from the top and must be moved inside the strip to reach their place; once placed, they cannot be moved again. Cargo loading applications impose similar constraints. This paper assumes that rectangles must be moved without rotation. For n rectangles, the resulting packing height is shown to have an asymptotic expected value of at least (0.31382733 ... )n under any on-line packing algorithm. An on-line algorithm is presented that achieves an asymptotic expected height of (0.36976421 ... )n. This algorithm improves the bound achieved in Next Fit Level (NFL) packing, by compressing the items packed on two successive levels of an NFL packing via on-line movement admissible under the Tetris-like constraint.