Abstract

We consider a multidimensional generalization of the bin packing problem, namely, packing 2-dimensional rectangles into the minimum number of unit squares, where 90 degree rotations are allowed. Our main contribution is a polynomial time algorithm for packing rectangles into at most OPT bins whose sides have length (1 + ?), for any ? > 0. Additionally, we show how this result can be used to obtain near optimal packing results for a variety of two and three dimensional packing problems in which 90 degree rotations are allowed. These include minimum rectangle packing, two dimensional strip packing, and the z-oriented 3-dimensional packing problem. © 2004.