請用此 Handle URI 來引用此文件: 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
摘要: 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
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。