Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
We analyze several “level-oriented” algorithms for packing rectangles into a unit-width, infinite-height bin so as to minimize the total height of the packing. For the three algorithms we discuss, we show that the ratio of the height obtained by the algorithm to the optimal height is asymptotically bounded, respectively, by 2, 1.7, and 1.5. The latter two improve substantially over the performance bounds for previously proposed algorithms. In addition, we give more refined bounds for special cases in which the widths of the given rectangles are restricted and in which only squares are to be packed.