New approximability and inapproximability results for 2-dimensional Bin Packing

ABSTRACT

We study the 2-dimensional generalization of the classical Bin Packing problem: Given a collection of rectangles of specified size (width, height), the goal is to pack these into minimum number of square bins of unit size. A long history of results exists for this problem and its special cases [3, 14, 10, 18, 9, 1, 15]. Currently, the best known approximation algorithm achieves a guarantee of 1.69 in the asymptotic case (i.e. when the optimum uses a large number of bins) [1]. However, an important open question has been whether 2-dimensional bin packing is essentially similar to the 1-dimensional case in that it admits an asymptotic polynomial time approximation scheme (APTAS) [8, 13] or not? We answer the question in the negative and show that the problem is APX hard in the asymptotic case. On the other hand, we give an asymptotic PTAS for the special case when all the rectangles to be packed are squares (or more generally hypercubes). This improves upon the previous best known guarantee of 1.454 for d = 2 [9] and 2 - (2/3)^d for d > 2 [15], and settles the approximability for this special case.

REFERENCES

• 1: 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
• 2: Chandra Chekuri , Sanjeev Khanna, On multi-dimensional packing problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.185-194, January 17-19, 1999, Baltimore, Maryland, United States
• 3: F. R. K. Chung, M. R. Garey, and D. S. Johnson. On packing two-dimensional bins. SIAM Journal on Algebraic and Discrete Methods, 3:66--76, 1982.
• 4: E. G. Coffman, Jr. , M. R. Garey , D. S. Johnson, Approximation algorithms for bin packing: a survey, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 5: E. G. Coffman, M. R. Garey, D. S. Johnson and R. E. Tarjan. Performance bounds for level-oriented two dimensional packing algorithms. SIAM J. Computing 9 (1980), pages 808--826.
• 6: José R. Correa , Claire Kenyon, Approximation schemes for multidimensional packing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 7: János Csirik , Gerhard J. Woeginger, On-line Packing and Covering Problems, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.147-177, January 1998
• 8: W. Fernandez de la Vega and G. Lueker. Bin packing can be solved within 1+ε in linear time. Combinatorica, 1:349--355, 1981.
• 9: Leah Epstein , Rob van Stee, Optimal online bounded space multidimensional packing, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 10: C. E. Ferreira, F. K. Miyazawa, and Y. Wakabayashi. Packing squares into squares. Pesquisa Operacional, 19(2):223--237, 1999.
• 11: Klaus Jansen , Guochaun Zhang, On rectangle packing: maximizing benefits, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 12: Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, v.37 n.1, p.27-35, Jan. 10, 1991 [doi>10.1016/0020-0190(91)90246-E]
• 13: N. Karmarkar and R. M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Foundations of Computer Science (FOCS), pages 312--320, 1982.
• 14: E. Remila, Approximate strip packing, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.31, October 14-16, 1996
• 15: Y. Kohayakawa, F. K. Miyazawa, P. Raghavan, and Y. Wakabayashi. Multidimensional cube packing. In Brazilian Symposium on Graphs, Algorithms and Combinatorics, 2001.
• 16: 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]
• 17: Erez Petrank, The hardness of approximation: gap location, Computational Complexity, v.4 n.2, p.133-157, April 1994 [doi>10.1007/BF01202286]
• 18: S. Seiden and R. van Stee. Newb ounds for multidimensional packing. Algorithmica, 36(3):261--293, 2003.
• 19: S. Sevastianov and G. Woeginger. Makespan minimization in open shops: a polynomial time approximation scheme. Networks and matroids; Sequencing and scheduling. Math. Programming, 82, no. 1--2, Ser. B:191--198, 1998.
• 20: Gerhard J. Woeginger, There is no asymptotic PTAS for two-dimensional vector packing, Information Processing Letters, v.64 n.6, p.293-297, Dec. 29, 1997 [doi>10.1016/S0020-0190(97)00179-8]