On the online bin packing problem

ABSTRACT

A new framework for analyzing online bin packing algorithms is presented. This framework presents a unified way of explaining the performance of algorithms based on the Harmonic approach. Within this framework, it is shown that a new algorithm, Harmonic++, has asymptotic performance ratio at most 1.58889. It is also shown that the analysis of Harmonic+1 presented in Richey [1991] is incorrect; this is a fundamental logical flaw, not an error in calculation or an omitted case. The asymptotic performance ratio of Harmonic+1 is at least 1.59217. Thus, Harmonic++ provides the best upper bound for the online bin packing problem to date.

REFERENCES

• 1: Brown, D. J.1979. A lower bound for on-line one-dimensional bin packing algorithms. Tech. Rep. R-864, Coordinated Sci. Lab., University of Illinois at Urbana-Champaign, Urbana, Ill.
• 2: 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
• 3: J. Csirik, An on-line algorithm for variable-sized bin packing, Acta Informatica, v.26 n.9, p.697-709, Oct. 1989
• 4: 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
• 5: János Csirik , Gerhard J. Woeginger, Resource Augmentation for Online Bounded Space Bin Packing, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.296-304, July 09-15, 2000
• 6: Johnson, D. S.1974. Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272--314.
• 7: Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., and Graham, R. L.1974. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 256--278.
• 8: 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]
• 9: Liang, F. M.1980. A lower bound for online bin packing. Info. Proc. Lett. 10, 76--79.
• 10: P. Ramanan , D. J. Brown , C. C. Lee , D. T. Lee, On-line bin packing in linear time, Journal of Algorithms, v.10 n.3, p.305-326, September 1989 [doi>10.1016/0196-6774(89)90031-X]
• 11: Michael B. Richey, Improved bounds for harmonic-based bin packing algorithms, Discrete Applied Mathematics, v.34 n.1-3, p.203-227, Nov. 1991 [doi>10.1016/0166-218X(91)90087-D]
• 12: Steven S. Seiden, An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing, SIAM Journal on Discrete Mathematics, v.14 n.4, p.458-470, 2001 [doi>10.1137/S0895480100369948]
• 13: Ullman, J. D.1971. The performance of a memory allocation algorithm. Tech. Rep. 100, Princeton University, Princeton, N.J., Oct.
• 14: 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]
• 15: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Design, Theory

Keywords:
Bin packing, online algorithms