ALCOMFT-TR-03-21

Joan Boyar and Lene M. Favrholdt
The Relative Worst Order Ratio for On-Line Bin Packing Algorithms
Århus. Work package 4. September 2003.

Abstract: The relative worst order ratio, a new measure for the quality of on-line algorithms, was previously defined by Boyar and Favrholdt. Classical bin packing algorithms such as First-Fit, Best-Fit, and Next-Fit were analyzed using this measure, giving results that are consistent with those previously obtained with the competitive ratio or the competitive ratio on accommodating sequences, but also giving new separations and easier results.

In this paper we consider newer algorithms; for the Classical Bin Packing Problem we analyze Harmonic(k), introduced by Lee and Lee, and some of its variants, and for the Dual Bin Packing Problem we introduce a new, simple, unfair variant of First-Fit.

Postscript file: ALCOMFT-TR-03-21.ps.gz (99 kb).