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 8 articles , 1 standard article )
Showing results 1 to 8 of 8.
- Reineke, Jan; Salinger, Alejandro: On the smoothness of paging algorithms (2018)
- Folwarczný, Lukáš; Sgall, Jiří: General caching is hard: even with small pages (2017)
- Brodal, Gerth Stølting; Moruz, Gabriel; Negoescu, Andrei: \textscOnlineMin: 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)
- Moruz, Gabriel; Negoescu, Andrei: Outperforming LRU via competitive analysis on parametrized inputs for paging (2012)