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.
The publication is available at portal.acm.org (subscription may be required).