TY - JOUR
T1 - On-line bin packing in linear time
AU - Ramanan, Prakash
AU - Brown, Donna J.
AU - Lee, C. C.
AU - Lee, D. T.
N1 - Funding Information:
*Part of this author’s work was performed when he was a graduate student at the University of Illinois, Urbana, IL. His work was supported in part by an IBM Graduate Fellowship. +This author’s work was supported by the National Science Foundation under Grant NSF IST So-12240 and the Joint Services Electronics Program (U.S. Army, U.S. Navy, and U.S. Air Force) under Contract NOOO14-79-C-0424. *This author’s work was supported in part by the National Science Foundation under Grant MC’S 83-42862.
PY - 1989/9
Y1 - 1989/9
N2 - In this paper, we study the 1-dimensional on-line bin packing problem. A list of pieces, each of size between zero and unity are to be packed, in order of their arrival, into a minimum number of unit-capacity bins. We present a new linear-time algorithm, the Modified Harmonic Algorithm and show, by a novel use of weighting functions, that it has an asymptotic worst-case performance ratio less than 3 2 + 1 9 + 1 222 = 1.(615)*. We show that for a large class of linear-time on-line algorithms including the Modified Harmonic Algorithm, the performance ratio is at least 3 2 + 1 9 = 1.61*. Then we show how to successively construct classes of improved linear-time on-line algorithms. For any algorithm in any of these classes, the performance ratio is at least 3 2 + 1 12 = 1.583*. We present an improved algorithm called Modified Harmonic-2 with performance ratio 1.612 ... and present an approach to construct linear-time on-line algorithms with better performance ratios. The analysis of Modified Harmonic-2 is omitted because it is very similar to that of Modified Harmonic, but it is substantially more complicated. Our results extend to orthogonal packings in two dimensions.
AB - In this paper, we study the 1-dimensional on-line bin packing problem. A list of pieces, each of size between zero and unity are to be packed, in order of their arrival, into a minimum number of unit-capacity bins. We present a new linear-time algorithm, the Modified Harmonic Algorithm and show, by a novel use of weighting functions, that it has an asymptotic worst-case performance ratio less than 3 2 + 1 9 + 1 222 = 1.(615)*. We show that for a large class of linear-time on-line algorithms including the Modified Harmonic Algorithm, the performance ratio is at least 3 2 + 1 9 = 1.61*. Then we show how to successively construct classes of improved linear-time on-line algorithms. For any algorithm in any of these classes, the performance ratio is at least 3 2 + 1 12 = 1.583*. We present an improved algorithm called Modified Harmonic-2 with performance ratio 1.612 ... and present an approach to construct linear-time on-line algorithms with better performance ratios. The analysis of Modified Harmonic-2 is omitted because it is very similar to that of Modified Harmonic, but it is substantially more complicated. Our results extend to orthogonal packings in two dimensions.
UR - http://www.scopus.com/inward/record.url?scp=38249007373&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249007373&partnerID=8YFLogxK
U2 - 10.1016/0196-6774(89)90031-X
DO - 10.1016/0196-6774(89)90031-X
M3 - Article
AN - SCOPUS:38249007373
SN - 0196-6774
VL - 10
SP - 305
EP - 326
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 3
ER -