Approximation schemes for multidimensional packing

ABSTRACT

We consider a classic multidimensional generalization of the bin packing problem, namely, packing d-dimensional rectangles into the minimum number of unit cubes. Our two results are: an asymptotic polynomial time approximation scheme for packing d-dimensional cubes into the minimum number of unit cubes and a polynomial time algorithm for packing rectangles into at most OPT bins whose sides have length (1 + ε), where OPT denotes the minimum number of unit bins required to pack the rectangles. Both algorithms also achieve the best possible additive constant term. For cubes, this settles the approximability of the problem and represents a significant improvement over the previous best known asymptotic approximation factor of 2 - (2/3)^d + ε. For rectangles, this contrasts with the currently best known approximation factor of 1.691....

REFERENCES

• 1: Nikhil Bansal , Maxim Sviridenko, New approximability and inapproximability results for 2-dimensional Bin Packing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 2: E. G. Coffman, Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan (1980). Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing 9, 808--826.
• 3: Alberto Caprara, Packing 2-Dimensional Bins in Harmony, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.490-499, November 16-19, 2002
• 4: A. Caprara, A. Lodi, and M. Monaci (2003). Fast Approximation Schemes for the Two-Stage, Two-Dimensional Bin Packing Problem. Research Report OR/03/6 DEIS.
• 5: W. Fernandez de la Vega and G. S. Lueker (1981). Bin packing can be solved within 1 + ε in polynomial time, Combinatorica 1, 349--355.
• 6: C. E. Ferreira, F. K. Miyazawa, and Y. Wakabayashi (1999). Packing squares into squares. Pesquisa Operacional 19, 349--355.
• 7: Claire Kenyon , Eric Rémila, A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem, Mathematics of Operations Research, v.25 n.4, p.645-656, November 2000 [doi>10.1287/moor.25.4.645.12118]
• 8: D. J. Kleitman and M. Krieger (1975). An optimal bound for two dimensional packing. In Proceeding of the 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS'75).
• 9: Y. Kohayakawa, F. K. Miyazawa, P. Raghavan, and Y. Wakabayashi (2001). Multidimensional Cube Packing, In Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2001).
• 10: Joseph Y.-T. Leung , Tommy W. Tam , C. S. Wong , Gilbert H. Young , Francis Y.L. Chin, Packing squares into a square, Journal of Parallel and Distributed Computing, v.10 n.3, p.271-275, Nov. 1990 [doi>10.1016/0743-7315(90)90019-L]
• 11: P. Novotny (1996). On packing of squares into a rectangle. Archivum Mathematicum 32, 75--83.
• 12: L. Moser (1965). Poorly formulated unsolved problems is combinatorial geometry. Mimeographed.
• 13: S. S. Seiden and R. van Stee (2003). New Bounds for Multidimensional Packing, Algorithmica 36, 261--293.
• 14: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001