Competitive analysis of randomized paging algorithms

DOI10.1007/3-540-61680-2_72MaRDI QIDQ4595503zbMATH OpenOpenAlexFDO

Authors J. Noga, D. Achlioptas, Marek Chrobak

Publication date 5 December 2017

Published in Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61680-2_72

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Analysis of algorithms (68W40) Theory of operating systems (68N25)

Recommendations

• Competitive analysis of randomized paging algorithms
• A strongly competitive randomized paging algorithm
• Competitive paging algorithms
• OnlineMin: a fast strongly competitive randomized paging algorithm
• \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm

Cited in

(22)

• More on randomized on-line algorithms for caching.
• Connection caching: Model and algorithms.
• Competitive paging algorithms
• scientific article; zbMATH DE number 1670537 (Why is no real title available?)
• The working set algorithm has competitive ratio less than two
• Competitive randomized algorithms for nonuniform problems
• Equitable Revisited
• scientific article; zbMATH DE number 1775453 (Why is no real title available?)
• Knowledge state algorithms
• \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm
• A competitive analysis for the start-gap algorithm for online memory wear leveling
• OnlineMin: a fast strongly competitive randomized paging algorithm
• New results for online page replication
• scientific article; zbMATH DE number 2080233 (Why is no real title available?)
• Trackless online algorithms for the server problem
• A randomized algorithm for two servers on the line.
• On randomization in on-line computation.
• On the influence of lookahead in competitive paging algorithms
• Parameterized Analysis of Paging and List Update Algorithms
• The complexity of paging against a probabilistic adversary
• scientific article; zbMATH DE number 65703 (Why is no real title available?)
• Limited bookmark randomized online algorithms for the paging problem

This page was built for publication: Competitive analysis of randomized paging algorithms

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