- The Relative Worst Order Ratio Applied to Paging.
- Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
In 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 718-727. ACM Press, 2005.
The relative worst order ratio, a new measure for the quality of
on-line algorithms, was recently defined and applied to two
bin packing problems.
Here, we apply it to the paging problem
and obtain the following results:
We devise a new deterministic paging algorithm, Retrospective-LRU, and
show that it performs better than LRU.
This is supported by experimental results, but contrasts with the
All deterministic marking algorithms have the same competitive ratio,
but here we find that LRU is better than FWF.
According to the relative worst order ratio, no deterministic marking algorithm
can be significantly better than
LRU, but the randomized algorithm MARK is better than LRU.
Finally, look-ahead is shown to be a significant advantage, in
contrast to the competitive ratio, which does not reflect that
look-ahead can be helpful.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The publication is available from ACM.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.