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 2081987145 2052713537 2013696768
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. This paper studies two approximation algorithms for packing rectangles, using the two-dimensional packing model of Baker, Coffman and Rivest [SIAM J. Comput., 9 (1980), pp. 846–855]. The algorithms studied are called next-fit and first-fit shelf algorithms, respectively. They differ from previous algorithms by packing the rectangles in the order given; the previous algorithms required sorting the rectangles by decreasing height or width before packing them, which is not possible in some applications. The shelf algorithms are a modification of the next-fit and first-fit decreasing height level algorithms of Coffman, Garey, Johnson and Tarjan [SIAM J. Comput., 9 (1980), pp. 808–826]. Each shelf algorithm takes a parameter r. It is shown that by choosing r appropriately, the asymptotic worst case performance of the shelf algorithms can be made arbitrarily close to that of the next-fit and first-fit level algorithms, without the restriction that items must be packed in order of decreasing height. Nonasymptoti... The paper considerspacking of rectanglesinto an infinite bin. Similar to theTetris game, the rectangles arrive from the top and, once placed, cannot be moved again. The rectangles are moved inside the bin to reach their place. For the case in which rotations are allowed, we design an algorithm whose performance ratio is constant. In contrast, if rotations are not allowed, we show that no algorithm of constant ratio exists. For this case we design an algorithm with performance ratio ofO(log(1 ?)), where ? is the minimum width of any rectangle. We also show that no algorithm can achieve a better ratio than?(log(1 ?))for this case. We present an asymptotic (2 + e)-approximation algorithm for the 3D-strip packing problem, for any e > 0. In the 3D-strip packing problem the input is a set L = b 1 , b 2 ,. . ., b n of 3-dimensional boxes. Each box b i has width, length, and height at most 1. The problem is to pack the boxes into a 3-dimensional bin B of width 1, length 1 and minimum height, so that the boxes do not overlap. We consider here only orthogonal packings without rotations; this means that the boxes are packed so that their faces are parallel to the faces of the bin, and rotations are not allowed. This algorithm improves on the previously best algorithm of Miyazawa and Wakabayashi which has asymptotic performance ratio of 2.64. Our algorithm can be easily modified to a (4 + e)-approximation algorithm for the 3D-bin packing problem.