New Algorithms for Bin Packing

Abstract

In the bin-packing problem a list L of n numbers are to be packed into unit-capacity bins. For any algorithm S, let r(S) be the maximum ratio S(L)/L^* for large L^*, where S(L) denotes the number of bins used by S and L^* denotes the minimum number needed. An on-line Ο(n log n)-time algorithm RFF with r(RFF) = 5/3 and an off-line polynomial-time algorithm RFFD with r(RFFD) ≤ 11/9 - ε for some fixed ε > 0, are given. These are strictly better, respectively, than two prominent algorithms: the First-Fit (FF), which is on-line with r(FF) = 17/10, and the First-Fit-Decreasing (FFD) with r(FFD) = 11/9. Furthermore, it is shown that any on-line algorithm S must have r(S) ≥ 3/2. The question, “How well can an ο(n log n)-time algorithm perform?” is also discussed. It is shown that in the generalized d-dimensional bin packing, any ο(n log n)-time algorithm S must have r(S) ≥ d.

References

1. 1 AHO, A.V, HOPCROFT, J.E, AND ULLMAN, J.D The Design and Analysts of Computer Algorithms Addison- Wesley, Reading, Mass, 1974.
2. 2 FREDERICKSON, G N, HECHT, M S., AND KIM, C E Approximate algorithms for some routing problems. SIAM J Comptg. 7 (1978), 178-193
3. 3 GAREY, M R, GRAHAM, R L., JOHNSON, D S, AND YAO, A C Multlprocessor scheduhng as generalized binpacking J Combmatortal Theory A 21 (1976), 257-298.
4. 4 GAgE'f, M.R., AND JOHNSON, D S The complexity ofnear-optmaal graph coloring. J. ACM 23, 1 (Jan. 1976), 43-49
5. 5 GRAHAM, R L Bounds on the performance of scheduling algorithms. In Computer and Job/Shop Scheduhng Theory, E G. Coffman, Jr, Ed, Wdey, New York, 1976, pp 165-227.
6. 6 JOHNSON, D S Near opttmal bm packing algonthm Ph D. Th., M I.T, Cambridge, Mass., June 1973
7. 7 JOHNSON, D S Fast algorithms for bm packing J. Comptr. Syst Sct 8 (1974), 272-314.
8. 8 JOHNSON, D.S, DEMERS, A., ULLMAN, J D, GAPEr, M.R, AND GRAHAM, R.L. Worst-ease performance bounds for smaple one-dunenslonal packing algorithms SIAM J. Comptg. 3 (1974), 299-325.
9. 9 KXRP, R M Reduc~bd~ty among eombmatonal problems. In Complexay of Computer Computatwns, R.E Mdler and J W. Thatcher, Eds, Plenum Press, New York, 1972, pp 85-103
10. 10 KNtrrH, D.E The Art of Computer Programming, Vol 3, Sorting and Searching Addison-Wesley, Reading, Mass, 1973
11. 11 ROSENKRANTZ, D J, STEARNS, R E., AND LEWlS, P.M An analysis of several heuristics for the traveling salesman problem SIAM Z Comptg 6 (1977), 563-58 I.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems