The working set algorithm has competitive ratio less than two

DOI10.1016/S0020-0190(97)00128-2MaRDI QIDQ287173zbMATH OpenOpenAlexFDO

Authors Sang Lyul Min, Yookun Cho, Kunsoo 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

zbMATH Keywords

analysis of algorithmscompetitive analysispage replacementworking set algorithm

Mathematics Subject Classification ID

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

Recommendations

• A strongly competitive randomized paging algorithm
• The working set model for program behavior
• Competitive paging algorithms
• Competitive analysis of randomized paging algorithms
• Competitive analysis of randomized paging algorithms

Cites work

• A Modified Working Set Paging Algorithm
• A strongly competitive randomized paging algorithm
• Competitive algorithms for server problems
• Competitive analysis of randomized paging algorithms
• Competitive paging algorithms
• Competitive randomized algorithms for nonuniform problems
• Competitive snoopy caching
• MIN—an optimal variable-space page replacement algorithm
• The Working Set Size Distribution for the Markov Chain Model of Program Behavior
• The working set model for program behavior
• Using page residency to select the working set parameter

Cited in

(1)

• The working set model for program behavior

This page was built for publication: The working set algorithm has competitive ratio less than two

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