OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm

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

In Proc. 9th Workshop on Approximation and Online Algorithms, volume 7164 of Lecture Notes in Computer Science, pages 164-175. Springer Verlag, Berlin, 2011.

Abstract

In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H_k on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present the first randomized paging approach that both has optimal competitiveness and selects victim pages in subquadratic time. In fact, if k pages fit in internal memory the best previous solution required O(k²) time per request and O(k) space, whereas our approach takes also O(k) space, but only O(log k) time in the worst case per page request.

Copyright notice

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

Online version

waoa11.pdf (177 Kb)

DOI

10.1007/978-3-642-29116-6_14

BIBT_EX entry

@incollection{waoa11,
  author = "Gerth Stølting Brodal and Gabriel Moruz and Andrei Negoescu",
  booktitle = "Proc. 9th Workshop on Approximation and Online Algorithms",
  doi = "10.1007/978-3-642-29116-6_14",
  isbn = "978-3-642-29115-9",
  pages = "164-175",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm",
  volume = "7164",
  year = "2011"
}