Abstract
The relative worst-order ratio is a measure of the quality of online
algorithms. In contrast to the competitive ratio, this measure
compares two online algorithms directly instead of
using an intermediate comparison with an optimal offline algorithm.
In this paper, we apply the relative worst-order ratio to online
algorithms for several common variants of the bin packing
problem.
We mainly consider pairs of algorithms that are not distinguished by
the competitive ratio and show that the relative worst-order ratio
prefers the intuitively better algorithm of each pair.
algorithms. In contrast to the competitive ratio, this measure
compares two online algorithms directly instead of
using an intermediate comparison with an optimal offline algorithm.
In this paper, we apply the relative worst-order ratio to online
algorithms for several common variants of the bin packing
problem.
We mainly consider pairs of algorithms that are not distinguished by
the competitive ratio and show that the relative worst-order ratio
prefers the intuitively better algorithm of each pair.
| Original language | English |
|---|---|
| Journal | Journal of Scheduling |
| Volume | 15 |
| Issue number | 1 |
| Pages (from-to) | 13-21 |
| Number of pages | 9 |
| ISSN | 1094-6136 |
| DOIs | |
| Publication status | Published - 2012 |