Multidimensional on-line bin packing: Algorithms and worst-case analysis (Q1123131)

This paper is concerned with the packing of rectangles into unit squares. An on-line algorithm with a worst-case performance ratio of 3.25 is presented. The algorithm is shown to achieve a performance ratio of 43/16 if the items to be packed are squares. Besides, the authors consider the multidimensional box-packing problem and prove that no on-line algorithm has a performance ratio better than 4/3 in the case when the items are all hypercubes.