Please use this identifier to cite or link to this item:
|標題:||On-Line Bin Packing in Linear Time||作者:||P.Ramanan
|出版社:||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.
|Appears in Collections:||資訊科學與工程學系所|
Show full item record
TAIR Related Article
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.