On-line bin packing in linear time

Prakash Ramanan*, Donna J. Brown, C. C. Lee, D. T. Lee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

95 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)305-326
Number of pages22
JournalJournal of Algorithms
Volume10
Issue number3
DOIs
StatePublished - Sep 1989

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'On-line bin packing in linear time'. Together they form a unique fingerprint.

Cite this