\textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm

DOI10.1007/s00224-012-9427-yzbMath1328.68311OpenAlexW1979064639MaRDI QIDQ2344206

Gerth Stølting Brodal, Andrei Negoescu, Gabriel Moruz

Publication date: 12 May 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9427-y

zbMATH Keywords

competitive analysison-line algorithmsrandomized algorithmspaging

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (3)

General caching is hard: even with small pages ⋮ On the smoothness of paging algorithms ⋮ OnlineMin

Cites Work

• Knowledge state algorithms
• A strongly competitive randomized paging algorithm
• Online algorithms. The state of the art
• Competitive snoopy caching
• Surpassing the information theoretic bound with fusion trees
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• More on randomized on-line algorithms for caching.
• Online algorithms: a survey
• Competitive analysis of randomized paging algorithms
• Organization and maintenance of large ordered indexes
• Dynamic ordered sets with exponential search trees
• Priority Search Trees
• Competitive paging algorithms
• Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
• Unnamed Item
• Unnamed Item

This page was built for publication: \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm