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

5th Italian Conference on Algorithms and Complexity (CIAC 2003)

We consider 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 94] and from the Random Order Ratio [Kenyon 96]
The new ratio is used to compare on-line algorithms directly by
taking the ratio of their performances on their
respective worst orderings of a worst-case sequence.
Two variants of the bin packing problem are considered: the Classical
Bin Packing Problem and the Dual Bin Packing Problem. Standard
algorithms are compared using this new measure.
For the Classical Bin Packing Problem, all algorithms considered can
be linearly ordered by this measure. For the Dual Bin Packing
problem some algorithms are found to be incomparable under
this new measure,
i.e., there are sequences where the one algorithm does better and sequences
where the other does better. Many results obtained are consistent with
those previously obtained with the competitive ratio or the competitive
ratio on accommodating sequences, but new separations and easier results
are also shown to be possible with the relative worst order ratio.

Last modified: May 5, 2003. Joan Boyar (joan@imada.sdu.dk)