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.
- 1 AHO, A.V, HOPCROFT, J.E, AND ULLMAN, J.D The Design and Analysts of Computer Algorithms Addison- Wesley, Reading, Mass, 1974. Google Scholar
- 2 FREDERICKSON, G N, HECHT, M S., AND KIM, C E Approximate algorithms for some routing problems. SIAM J Comptg. 7 (1978), 178-193Google Scholar
- 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.Google Scholar
- 4 GAgE'f, M.R., AND JOHNSON, D S The complexity ofnear-optmaal graph coloring. J. ACM 23, 1 (Jan. 1976), 43-49 Google Scholar
- 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.Google Scholar
- 6 JOHNSON, D S Near opttmal bm packing algonthm Ph D. Th., M I.T, Cambridge, Mass., June 1973Google Scholar
- 7 JOHNSON, D S Fast algorithms for bm packing J. Comptr. Syst Sct 8 (1974), 272-314.Google Scholar
- 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.Google Scholar
- 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-103Google Scholar
- 10 KNtrrH, D.E The Art of Computer Programming, Vol 3, Sorting and Searching Addison-Wesley, Reading, Mass, 1973Google Scholar
- 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.Google Scholar
Index Terms
- New Algorithms for Bin Packing
Recommendations
Online algorithms for 1-space bounded 2-dimensional bin packing and square packing
In this paper, we study 1-space bounded 2-dimensional bin packing and square packing. A sequence of rectangular items (square items) arrive one by one, each item must be packed into a square bin of unit size on its arrival without any information about ...
Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing
In this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d -dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side ...
Comments