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

DOI10.1007/S00224-012-9427-YMaRDI QIDQ2344206zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

randomized algorithmscompetitive analysison-line algorithmspaging

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(12)

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

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)