Near-Optimal Solutions to Two-Dimensional Bin Packing With 90 Degree Rotations

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.