On the Sum-of-Squares algorithm for bin packing

ABSTRACT

In this article we present a theoretical analysis of the online Sum-of-Squares algorithm (SS) for bin packing along with several new variants. SS is applicable to any instance of bin packing in which the bin capacity B and item sizes s(a) are integral (or can be scaled to be so), and runs in time O(nB). It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, SS also has sublinear expected waste. For any discrete distribution where the optimal expected waste is bounded, SS has expected waste at most O(log n). We also discuss several interesting variants on SS, including a randomized O(nB log B)-time online algorithm SS* whose expected behavior is essentially optimal for all discrete distributions. Algorithm SS* depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution F, just what is the growth rate for the optimal expected waste.

REFERENCES

• 1: Susanne Albers , Michael Mitzenmacher, Average-case analyses of first fit and random fit bin packing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.290-299, January 25-27, 1998, San Francisco, California, United States
• 2: Alon, N., and Spencer, J. H. 1992. The Probabilistic Method. Wiley Interscience, New York, NY.
• 3: Applegate, D. L., Buriol, L., Dillard, B., Johnson, D. S., and Shor, P. W. 2003. The cutting-stock approach to bin-packing: Theory and experiments. In Proceedings of the 5th Workshop on Algorithm Engineering and Experimentation. SIAM, Philadelphia, PA, 1--15.
• 4: E. G. Coffman, Jr. , C. Courcoubetis , M. R. Garey , D. S. Johnson , L. A. McGeoch , P. W. Shor , R. R. Weber , M. Yannakakis, Fundamental discrepancies between average-case analyses under discrete and continuous distributions: a bin packing case study, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.230-240, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103446]
• 5: E. G. Coffman, Jr. , C. Courcoubetis , M. R. Garey , D. S. Johnson , P. W. Shor , R. R. Weber , M. Yannakakis, Bin Packing with Discrete Item Sizes, Part I: Perfect Packing Theorems and the Average Case Behavior of Optimal Packings, SIAM Journal on Discrete Mathematics, v.13 n.3, p.384-402, May—June 2000 [doi>10.1137/S0895480197325936]
• 6: E. G. Coffman, Jr. , C. Courcoubetis , M. R. Garey , D. S. Johnson , P. W. Shor , R. R. Weber , M. Yannakakis, Perfect Packing Theorems and the Average-Case Behavior of Optimal and Online Bin Packing, SIAM Review, v.44 n.1, p.95-108, 2002 [doi>10.1137/S0036144501395423]
• 7: Coffman, Jr., E. G., Johnson, D. S., McGeoch, L. A., Shor, P. W., and Weber, R. R. 2005. Bin packing with discrete item sizes, Part III: Average case behavior of FFD and BFD. In preparation.
• 8: E. G. Coffman, Jr. , D. S. Johnson , P. W. Shor , R. R. Weber, Markov chains, computer proofs, and average-case analysis of best fit bin packing, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.412-421, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167203]
• 9: E. G. Coffman, Jr. , D. S. Johnson , P. W. Shor , R. R. Weber, Bin packing with discrete item sizes, part II: tight bounds on first fit, Random Structures & Algorithms, v.10 n.1-2, p.69-101, Jan.–March 1997 [doi>10.1002/(SICI)1098-2418(199701/03)10:1/2<69::AID-RSA4>3.0.CO;2-V]
• 10: Courcoubetis, C., and Weber, R. R. 1990. Stability of online bin-packing with random arrivals and long-run average constraints. Prob. Eng. Inf. Sci. 4, 447--460.
• 11: Janos Csirik , David S. Johnson , Claire Kenyon, Better approximation algorithms for bin covering, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.557-566, January 07-09, 2001, Washington, D.C., United States
• 12: Csirik, J., Johnson, D. S., and Kenyon, C. 2005. On the worst-case performance of the sum-of-squares algorithm for bin-packing. E-Print arXiv:cs.DS/0509031, arXiv.org e-Print archive (http://arxiv.org/archive/cs).
• 13: János Csirik , David S. Johnson , Claire Kenyon , Peter W. Shor , Richard R. Weber, A Self Organizing Bin Packing Heuristic, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.246-265, January 15-16, 1999
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Gilmore, P. C., and Gomory, R. E. 1961. A linear programming approach to the cutting stock problem. Oper. Res. 9, 849--859.
• 16: Gilmore, P. C., and Gomory, R. E. 1963. A linear programming approach to the cutting stock program---Part II. Oper. Res. 11, 863--888.
• 17: Grötschel, M., Lovasz, L., and Schrijver, A. 1981. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169--197.
• 18: Hajek, B. 1982. Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Prob. 14, 502--525.
• 19: 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, 299--325.
• 20: Karmarkar, N., and Karp, R. M. 1982. An efficient approximation scheme for the one-dimensional bin-packing problem. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, Calif., 312--320.
• 21: Karp, R. M., and Papadimitriou, C. H. 1982. On the linear characterization of combinatorial optimization problems. SIAM J. Comput. 11, 620--632.
• 22: C. Kenyon , M. Mitzenmacher, Linear waste of best fit bin packing on skewed distributions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.582, November 12-14, 2000
• 23: Claire Kenyon , Yuval Rabani , Alistair Sinclair, Biased random walks, Lyapunov functions, and stochastic analysis of best fit bin packing, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.351-358, January 28-30, 1996, Atlanta, Georgia, United States
• 24: Wansoo T. Rhee, Optimal bin packing with items of random sizes, Mathematics of Operations Research, v.13 n.1, p.140-151, February 1988 [doi>10.1287/moor.13.1.140]
• 25: Wansoo T. Rhee , Michel Talagrand, On line bin packing with items of random size, Mathematics of Operations Research, v.18 n.2, p.438-445, May 1993 [doi>10.1287/moor.18.2.438]
• 26: Wansoo T. Rhee , Michel Talagrand, On-line bin packing of items of random sizes, II, SIAM Journal on Computing, v.22 n.6, p.1251-1256, Dec. 1993 [doi>10.1137/0222074]
• 27: Vaidya, P. M. 1989. Speeding-up linear programming using fast matrix multiplication. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, 332--337.
• 28: Valério de Carvalho, J. M. 1999. Exact solutions of bin-packing problems using column generation and branch and bound. Ann. Oper. Res. 86, 629--659.
• 29: 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]

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Approximation algorithms, average case analysis, bin packing