HARMONIC: AN EFFICIENT ONLINE BIN-PACKING.

Chung Chieh Lee*, D. T. Lee

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The one-dimensional online bin packing is considered. A simple O(n)-time and O(1)-space algorithm called HARMONIC is presented. It is proved that this algorithm can achieve a worst-case performance ratio smaller than 1. 692, which is better than that of the O(nlogn)-time and O(n)-space algorithm FIRST FIT. It is proved that 1. 691. . . is a lower bound for all O(1)-space online bin packing algorithms. Then a revised version of HARMONIC called REFINED-HARMONIC is presented. This algorithm retains the O(n)-time advantage while improving the worst-case performance ratio to 1. 6359. . . at the expense of space complexity. A more sophisticated O(n)-time algorithm achieving a low worst-case performance ratio of 1. 612. . . is presented.

Original languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherPrinceton Univ, Dep of Electrical Engineering & Computer Science
Pages323-327
Number of pages5
StatePublished - Dec 1 1984

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'HARMONIC: AN EFFICIENT ONLINE BIN-PACKING.'. Together they form a unique fingerprint.

Cite this