OnlineMin: A fast strongly competitive randomized paging algorithm. 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 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(k 2 ) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(logk) worst case time and O(logk/loglogk) worst case time per page request respectively.
Keywords for this software
References in zbMATH (referenced in 6 articles , 1 standard article )
Showing results 1 to 6 of 6.
- Folwarczný, Lukáš; Sgall, Jiří: General caching is hard: even with small pages (2017)
- Brodal, Gerth Stølting; Moruz, Gabriel; Negoescu, Andrei: OnlineMin: a fast strongly competitive randomized paging algorithm (2015)
- Epstein, Leah; Imreh, Csanád; Levin, Asaf; Nagy-György, Judit: Online file caching with rejection penalties (2015)
- Kovács, Annamária; Meyer, Ulrich; Moruz, Gabriel; Negoescu, Andrei: The optimal structure of algorithms for $\alpha$-paging (2015)
- Moruz, Gabriel; Negoescu, Andrei; Neumann, Christian; Weichert, Volker: Engineering efficient paging algorithms (2014)
- Brodal, Gerth Stølting; Moruz, Gabriel; Negoescu, Andrei: OnlineMin: a fast strongly competitive randomized paging algorithm (2012)