Optimal online bounded space multidimensional packing

ABSTRACT

We solve an open problem in the literature by providing an online algorithm for multidimensional bin packing that uses only bounded space. To achieve this, we introduce a new technique for classifying the items to be packed. We show that our algorithm is optimal among bounded space algorithms for any dimension d > 1. Its asymptotic performance ratio is (II∞)^d, where II∞ ≈ 1:691 is the asymptotic performance ratio of the one-dimensional algorithm HARMONIC. A modified version of this algorithm for the case where all items are hypercubes is also shown to be optimal. Its asymptotic performance ratio is sublinear in d.Additionally, for the special case of packing squares in two-dimensional bins, we present a new unbounded space online algorithm with asymptotic performance ratio of at most 2.271. We also present an approximation algorithm for the offline problem with approximation ratio of 16/11.

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: David Blitz, André van Vliet, and Gerhard J. Woeginger. Lower bounds on the asymptotic worst-case ratio of online bin packing algorithms. Unpublished manuscript, 1996.
• 3: Donna J. Brown. A lower bound for on-line one-dimensional bin packing algorithms. Technical Report R-864, Coordinated Sci. Lab., Urbana, Illinois, 1979.
• 4: 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
• 5: Fan R. K. Chung, Michael R. Garey, and David S. Johnson. On packing two-dimensional bins. SIAM Journal on Algebraic and Discrete Methods, 3:66--76, 1982.
• 6: 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
• 7: Don Coppersmith and Prabhakar Raghavan. Multidimensional online bin packing: Algorithms and worst case analysis. Operations Research Letters, 8:17--20, 1989.
• 8: 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
• 9: J. Csirik , J. B. G. Frenk , M. Labbé, Two-dimensional rectangle packing: on-line methods and results, Discrete Applied Mathematics, v.45 n.3, p.197-204, Sept. 7, 1993 [doi>10.1016/0166-218X(93)90009-D]
• 10: János Csirik and André van Vliet. An on-line algorithm for multidimensional bin packing. Operations Research Letters, 13(3):149--158, Apr 1993.
• 11: 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
• 12: Wenceslas Fernandez de la Vega and George S. Lueker. Bin packing can be solved within 1 + ε in linear time. Combinatorica, 1:349--355, 1981.
• 13: Carlos E. Ferreira, Flavio K. Miyazawa, and Yoshiko Wakabayashi. Packing squares into squares. Pesquisa Operacional, 19(2):223--237, 1999.
• 14: G. Galambos, A 1.6 lower-bound for the two-dimensional on-line rectangle bin-packing, Acta Cybernetica, v.10 n.1-2, p.21-24, Sept. 1991
• 15: Gabor Galambos and André van Vliet. Lower bounds for 1-, 2-, and 3-dimensional online bin packing algorithms. Computing, 52:281--297, 1994.
• 16: M. R. Garey , R. L. Graham , J. D. Ullman, Worst-case analysis of memory allocation algorithms, Proceedings of the fourth annual ACM symposium on Theory of computing, p.143-150, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804907]
• 17: David S. Johnson. Fast algorithms for bin packing. Journal Computer Systems Science, 8:272--314, 1974.
• 18: Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 312--320, 1982.
• 19: Yoshiharu Kohayakawa, Flavio K. Miyazawa, Prabhakar Raghavan, and Yoshiko Wakabayashi. Multidimensional cube packing. In Jayme Szwarcfiter and Siang Song, editors, Electronic Notes in Discrete Mathematics, volume 7. Elsevier Science Publishers, 2001.
• 20: C. C. Lee , D. T. Lee, A simple on-line bin-packing algorithm, Journal of the ACM (JACM), v.32 n.3, p.562-572, July 1985 [doi>10.1145/3828.3833]
• 21: K. Li and K. H. Cheng. A generalized harmonic algorithm for on-line multi-dimensional bin packing. manuscript, 1990.
• 22: Frank M. Liang. A lower bound for online bin packing. Information Processing Letters, 10:76--79, 1980.
• 23: F. K. Miyazawa , Y. Wakabayashi, Cube packing, Theoretical Computer Science, v.297 n.1-3, p.355-366, 17 March 2003 [doi>10.1016/S0304-3975(02)00647-3]
• 24: Steven S. Seiden, On the online bin packing problem, Journal of the ACM (JACM), v.49 n.5, p.640-671, September 2002 [doi>10.1145/585265.585269]
• 25: Steve S. Seiden and Rob van Stee. New bounds for multidimensional packing. Algorithmica, 36(3):261--293, 2003.
• 26: Jeffrey D. Ullman. The performance of a memory allocation algorithm. Technical Report 100, Princeton University, Princeton, NJ, 1971.
• 27: André van Vliet, An improved lower bound for on-line bin packing algorithms, Information Processing Letters, v.43 n.5, p.277-284, Oct. 5, 1992 [doi>10.1016/0020-0190(92)90223-I]
• 28: André van Vliet. Lower and upper bounds for online bin packing and scheduling heuristics. PhD thesis, Erasmus University, Rotterdam, The Netherlands, 1995.
• 29: André van Vliet, On the asymptotic worst case behavior of harmonic fit, Journal of Algorithms, v.20 n.1, p.113-136, Jan. 1996 [doi>10.1006/jagm.1996.0005]
• 30: Gerhard Woeginger, Improved space for bounded-space, on-line bin-packing, SIAM Journal on Discrete Mathematics, v.6 n.4, p.575-581, Nov. 1993 [doi>10.1137/0406045]
• 31: Andrew Chi-Chih Yao, New Algorithms for Bin Packing, Journal of the ACM (JACM), v.27 n.2, p.207-227, April 1980 [doi>10.1145/322186.322187]