Aarhus University Seal

OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Gerth Stølting Brodal
  • Gabriel Moruz, Goethe University Frankfurt, Germany
  • Andrei Negoescu, Goethe University Frankfurt, Germany
n 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 2) time per request and O(k) space, whereas our approach takes also O(k) space, but only O(logk) time in the worst case per page request.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to) 164-175
Number of pages12
Publication statusPublished - 2012
Event9thWorkshop on Approximation and Online Algorithms - Saarbrücken, Germany
Duration: 8 Sept 20119 Sept 2011
Conference number: 9


Workshop9thWorkshop on Approximation and Online Algorithms

Bibliographical note

Title of the vol.: Approximation and Online Algorithms : 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers / ed. by Roberto Solis-Oba, Giuseppe Persiano
ISBN: 978-3-642-29115-9. Online ISBN 978-3-642-29116-6

See relations at Aarhus University Citationformats

ID: 41505447