On-Line Bin Packing in Linear Time

Abstract

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.