**The Relative Worst Order Ratio for On-Line Algorithms***Joan Boyar, Lene M. Favrholdt*

ACM Transactions on Algorithms

We define a new measure for the quality of on-line algorithms,
the *relative worst order ratio*, using ideas from the Max/Max
ratio
[Ben-David,Borodin 1994] and from the random order ratio [Kenyon
1996].
The new ratio is used to compare on-line algorithms directly by
taking the ratio of their performances on their
respective worst permutations of a worst-case sequence.

Two variants of the bin packing problem are considered: the Classical Bin Packing problem, where the goal is to fit all items in as few bins as possible, and the Dual Bin Packing problem, which is the problem of maximizing the number of items packed in a fixed number of bins. Several known algorithms are compared using this new measure, and a new, simple variant of First-Fit is proposed for Dual Bin Packing.

Many of our results are consistent with those previously obtained with the competitive ratio or the competitive ratio on accommodating sequences, but new separations and easier proofs are found.

Last modified: Mon May 22 16:12:27 CEST 2006 Joan Boyar (joan@imada.sdu.dk)