Xin Han
Abstract
The 2D Online Bin Packing is a fundamental problem in Computer Science and the determination of its asymptotic competitive ratio has research attention. In a long series of papers, the lower bound of this ratio has been improved from 1.808, 1.856 to 1.907 and its upper bound reduced from 3.25, 3.0625, 2.8596, 2.7834 to 2.66013. In this article, we rewrite the upper bound record to 2.5545. Our idea for the improvement is as follows.
In 2002, Seiden and van Stee [Seiden and van Stee 2003] proposed an elegant algorithm called H ⊗ C, comprised of the Harmonic algorithm H and the Improved Harmonic algorithm C, for the two-dimensional online bin packing problem and proved that the algorithm has an asymptotic competitive ratio of at most 2.66013. Since the best known online algorithm for one-dimensional bin packing is the Super Harmonic algorithm [Seiden 2002], a natural question to ask is: could a better upper bound be achieved by using the Super Harmonic algorithm instead of the Improved Harmonic algorithm? However, as mentioned in Seiden and van Stee [2003], the previous analysis framework does not work. In this article, we give a positive answer for this question. A new upper bound of 2.5545 is obtained for 2-dimensional online bin packing. The main idea is to develop new weighting functions for the Super Harmonic algorithm and propose new techniques to bound the total weight in a rectangular bin.
- Bansal, N., Caprara, A., and Sviridenko, M. 2009. A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput. 39, 4, 1256--1278. Google Scholar
Digital Library
- Bansal, N., Correa, J. R., Kenyon, C., and Sviridenko, M. 2006. Bin packing in multiple dimensions: Inapproximability results and approximation schemes. Math. Oper. Res. 31, 1, 31--49. Google ScholarDigital Library
- Blitz, D., van Vliet, A., and Woeginger, G. J. 1996. Lower bounds on the asymptotic worst-case ratio of online bin packing alorithms. Unpublished manuscript.Google Scholar
- Brown, D. 1979. A lower bound for on-line one-dimensional bin packing algorithms. Tech. rep. R864, Coordinated Science Lab., Urbana, Illinois.Google Scholar
- Caprara, A. 2002. Packing 2-dimensional bins in harmony. In Proceedings of the Symposium on Foundations of Computer Science (FOCS). 490--499. Google ScholarDigital Library
- Chung, F., Garey, M., and Johnson, D. 1982. On packing two-dimensional bins. SIAM J. Alg. Disc. Meth. 3, 1, 66--76.Google ScholarCross Ref
- Coffman, E., Garey, M., and Johnson, D. 1987. Approximation Algorithms for Bin Packing: A Survey, chapter 2. PWS, Boston, MA.Google Scholar
- Coppersmith, D. and Paghavan, P. 1989. Multidimensional on-line bin packing: Algorithms and worst case analysis. Oper. Res. Lett 8, 17--20.Google ScholarDigital Library
- Csirik, J., Frenk, J. B. G., and Labbé, M. 1993. Two-dimensional rectangle packing: On-line methods and results. Disc. Appl. Math. 45, 3, 197--204. Google ScholarDigital Library
- Csirik, J. and van Vliet, A. 1993. An on-line algorithm for multidimensional bin packing. Oper. Res. Lett 13, 149--158.Google ScholarDigital Library
- Epstein, L. and van Stee, R. 2004. Optimal online bounded space multidimensional packing. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'04). 214--223. Google ScholarDigital Library
- Epstein, L. and van Stee, R. 2005a. Online square and cube packing. Acta Inf. 41, 9.Google ScholarDigital Library
- Epstein, L. and van Stee, R. 2005b. Optimal online algorithms for multidimensional packing problems. SIAM J. Comput. 35, 2, 431--448. Google ScholarDigital Library
- Galambos, G. 1991. A 1.6 lower-bound for the two-dimensional on-line rectange bin-packing. Acta Cybern. 10, 1-2, 21--24. Google ScholarDigital Library
- Galambos, G. and van Vliet, A. 1994. Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms. Computing 52, 3, 281--297.Google ScholarCross Ref
- GLP. http://www.gnu.org/software/glpk.Google Scholar
- Han, X., Fujita, S., and Guo, H. 2001. A two-dimensional harmonic algorithm with performance ratio 2.7834. IPSJ SIG Notes 93, 43--50.Google Scholar
- Han, X., Ye, D., and Zhou, Y. 2006. Improved online hypercube packing. In Proceedings of the 4th Workshop on Approximation and Online Algorithms (WAOA). 226--239. Google ScholarDigital Library
- Johnson, D., Demers, A., Ullman, J., Garey, M., and Graham, R. 1974. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 4, 299--325.Google ScholarDigital Library
- Lee, C. and Lee, D. 1985. A simple on-line packing algorithm. J. ACM 32, 562--572. Google ScholarDigital Library
- Liang, F. 1980. A lower bound for online bin packing. Inf. Proc. Lett. 10, 76--79.Google ScholarCross Ref
- Miyazawa, F. and Wakabayashi, Y. 2003. Cube packing. Theoret. Comput. Sci. 297, 1--3, 355--366. Google ScholarDigital Library
- Ramanan, P., Brown, D., Lee, C., and Lee, D. 1989. On-line bin packing in linear time. J. Algor. 10, 305--326. Google ScholarDigital Library
- Seiden, S. 2002. On the online bin packing. J. ACM 49, 640--671. Google ScholarDigital Library
- Seiden, S. and van Stee, R. 2003. New bounds for multidimensional packing. Algorithmica 36, 261--293.Google ScholarDigital Library
- van Vliet, A. 1992. An improved lower bound for on-line bin packing algorithms. Inf. Proc. Letters. 43, 277--284. Google ScholarDigital Library
- van Vliet, A. 1995. Lower and upper bounds for online bin packing and scheduling heuristics. Ph.D. dissertation. Erasmus University.Google Scholar
- Yao, A.-C. 1980. New algorithms for bin. J. ACM 27, 207--227. Google ScholarDigital Library
Recommendations
Tight bounds for online vector bin packing
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of ComputingIn the d-dimensional bin packing problem (VBP), one is given vectors x1,x2, ... ,xn ∈ Rd and the goal is to find a partition into a minimum number of feasible sets: {1,2 ... ,n} = ∪is Bi. A set Bi is feasible if ∑j ∈ Bi xj ≤ 1, where 1 denotes the all 1'...
A new upper bound for the online square packing problem in a strip
In this paper we consider the online problem of packing a list of squares into one strip of width 1 and infinite length without overlap so as to minimize the required height of the packing. We derive an upper bound 5 on the competitive ratio for this ...
Online Results for Black and White Bin Packing
In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each ...
Comments