Abstract
We consider a new measure for the quality of on-line algorithms, the relative worst order ratio, using ideas from the Max/Max ratio [2] and from the random order ratio [8]. 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. Many of the results obtained here 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.
| Original language | English |
|---|---|
| Title of host publication | 5th Italian Conference on Algorithms and Complexity (CIAC 2003) |
| Editors | R., red. Petreschi, G., red. Persiano, R., red. Silvestri |
| Volume | 2653 |
| Publisher | Springer |
| Publication date | 2003 |
| Pages | 58-69 |
| Publication status | Published - 2003 |
| Event | 5th Italian Conference on Algorithms and Complexity (CIAC 2003) - , Italy Duration: 24. Aug 2010 → … Conference number: 5 |
Conference
| Conference | 5th Italian Conference on Algorithms and Complexity (CIAC 2003) |
|---|---|
| Number | 5 |
| Country/Territory | Italy |
| Period | 24/08/2010 → … |
| Series | Lecture Notes in Computer Science |
|---|---|
| Volume | 2653 |