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

Abstract

We consider the problem of packing rectangles into bins which are unit squares. We give an on-line algorithm that uses at most 3.25 times the optimal number of bins. We also prove a result for the case when the items to be packed are squares and discuss extensions to higher dimensions. © 1989.