Two- and three-dimensional packings with orthogonal rotations

We present approximation algorithms for the following packing problems: the two-dimensional strip packing problem, the two-dimensional bin packing problem, the three-dimensional strip packing problem, and the three-dimensional bin packing problem. For all these problems, we consider orthogonal packings where ninety-degree rotations are allowed. The algorithms we show for these problems have asymptotic performance bounds 1.613, 2.64, 2.76 and 4.89, respectively. We also present an algorithm for the z-oriented three-dimensional strip packing problem with asymptotic performance bound 2.64. To our knowledge, these are the best bounds known for each problem.

2004