Markov Paging

DOI10.1137/S0097539794268042zbMath0966.68053OpenAlexW2914415689MaRDI QIDQ4507377

Anna R. Karlin, Prabhakar Raghavan, Steven J. Phillips

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794268042

zbMATH Keywords

Markov chainscompetitive analysispaginglocality of reference

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Related Items (18)

Online-bounded analysis ⋮ Competitive caching of query results in search engines ⋮ On the relative dominance of paging algorithms ⋮ Quantifying Competitiveness in Paging with Locality of Reference ⋮ A universal online caching algorithm based on pattern matching ⋮ Evaluating the quality of online optimization algorithms by discrete event simulation ⋮ Online network design with outliers ⋮ The relative worst-order ratio applied to paging ⋮ Optimal eviction policies for stochastic address traces ⋮ Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ Markov incremental constructions ⋮ Online Bounded Analysis ⋮ Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis ⋮ Relative interval analysis of paging algorithms on access graphs ⋮ Quantifying competitiveness in paging with locality of reference ⋮ Parameterized analysis of paging and list update algorithms ⋮ Data structures on event graphs

This page was built for publication: Markov Paging