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

- Engineering(all)