OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm

Gerth Stølting Brodal, Gabriel Moruz, and Andrei Negoescu

In Theory of Computing Systems, Special issue of the 9th Workshop on Approximation and Online Algorithms, volume 56(1), pages 22-40, 2015.

Abstract

In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of Hk on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present a new randomized paging algorithm OnlineMin that has optimal competitiveness and allows fast implementations. In fact, if k pages fit in internal memory the best previous solution required O(k2) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(log k) worst case time and O(log k/log log k) worst case time per page request respectively.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2015. All rights reserved.

Online version

tocs15.pdf (242 Kb)

DOI

10.1007/s00224-012-9427-y

BIBTEX entry

@article{tocs15,
  author = "Gerth St{\o}lting Brodal and Gabriel Moruz and Andrei Negoescu",
  doi = "10.1007/s00224-012-9427-y",
  issn = "1432-4350",
  journal = "Theory of Computing Systems, Special issue of the 9th Workshop on Approximation and Online Algorithms",
  number = "1",
  pages = "22-40",
  title = "OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm",
  volume = "56",
  year = "2015"
}

Other versions