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 language | English (US) |
|---|---|
| Title of host publication | Unknown Host Publication Title |
| Publisher | Princeton Univ, Dep of Electrical Engineering & Computer Science |
| Pages | 323-327 |
| Number of pages | 5 |
| State | Published - Dec 1 1984 |
ASJC Scopus subject areas
- General Engineering