The working set algorithm has competitive ratio less than two
From MaRDI portal
Publication:287173
DOI10.1016/S0020-0190(97)00128-2zbMath1336.68321OpenAlexW2000192615MaRDI QIDQ287173
Sang Lyul Min, Yookun Cho, Kun Soo Park
Publication date: 26 May 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00128-2
Analysis of algorithms (68W40) Randomized algorithms (68W20) Theory of operating systems (68N25) Online algorithms; streaming algorithms (68W27)
Cites Work
- A strongly competitive randomized paging algorithm
- Competitive snoopy caching
- Competitive randomized algorithms for nonuniform problems
- Using page residency to select the working set parameter
- Competitive algorithms for server problems
- The Working Set Size Distribution for the Markov Chain Model of Program Behavior
- Competitive paging algorithms
- MIN—an optimal variable-space page replacement algorithm
- A Modified Working Set Paging Algorithm
- Competitive analysis of randomized paging algorithms
- The working set model for program behavior