Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/38367
標題: On-Line Bin Packing in Linear Time
作者: P.Ramanan
D.J.Brown
C.C.Lee
D.T.Lee
出版社: Academic Press, Inc. Duluth, MN, USA
Project: J. Algorithms, Volume�10, Issue�3, Page(s) �305-326.
摘要: 
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 View the MathML source. We show that for a large class of linear-time on-line algorithms including the Modified Harmonic Algorithm, the performance ratio is at least View the MathML source. 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 View the MathML source. 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.
URI: http://hdl.handle.net/11455/38367
ISSN: 0196-6774
DOI: 10.1016/0196-6774(89)90031-X
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.