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

DOI10.1007/S00224-012-9427-YzbMATH Open1328.68311OpenAlexW1979064639MaRDI QIDQ2344206FDOQ2344206

Authors: Gerth Stølting Brodal, Gabriel Moruz, Andrei Negoescu 

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

Recommendations

• OnlineMin: a fast strongly competitive randomized paging algorithm
• A strongly competitive randomized paging algorithm
• Competitive analysis of randomized paging algorithms
• Competitive analysis of randomized paging algorithms
• Improved space bounds for strongly competitive randomized paging algorithms

zbMATH Keywords

randomized algorithmscompetitive analysison-line algorithmspaging

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• On the smoothness of paging algorithms
• OnlineMin: a fast strongly competitive randomized paging algorithm
• Improved space bounds for strongly competitive randomized paging algorithms
• Competitive paging algorithms
• Knowledge state algorithms
• Randomized online multi-threaded paging
• Limited bookmark randomized online algorithms for the paging problem
• Competitive analysis of randomized paging algorithms
• OnlineMin
• Engineering efficient paging algorithms
• A primal-dual randomized algorithm for weighted paging
• General caching is hard: even with small pages
• Paging on a RAM with Limited Resources
• Online min-max paging

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344206)