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|
|Number of pages||5|
|State||Published - Dec 1 1984|
ASJC Scopus subject areas