Competitive analysis of randomized paging algorithms

DOI10.1007/3-540-61680-2_72zbMATH Open1379.68376OpenAlexW2168823865MaRDI QIDQ4595503FDOQ4595503

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)

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

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)