On the relative dominance of paging algorithms

DOI10.1016/j.tcs.2009.04.023zbMath1171.68046MaRDI QIDQ837160

Alejandro López-Ortiz, J. Ian Munro, Reza Dorrigiv

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.023

zbMATH Keywords

competitive analysisonline algorithmspagingfault rate

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

Related Items

Online Bounded Analysis, Relative Worst-Order Analysis: A Survey, A comparison of performance measures for online algorithms, A theoretical comparison of LRU and LRU-K, On the separation and equivalence of paging strategies and other online algorithms, Online-bounded analysis, Evaluating the quality of online optimization algorithms by discrete event simulation, Quantifying competitiveness in paging with locality of reference, Exact distributional analysis of online algorithms with lookahead, Parameterized analysis of paging and list update algorithms, A comparison of performance measures via online search, Relative interval analysis of paging algorithms on access graphs, The Frequent Items Problem in Online Streaming Under Various Performance Measures, Quantifying Competitiveness in Paging with Locality of Reference

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The relative worst-order ratio applied to paging
• LRU is better than FIFO
• A new measure for the study of on-line algorithms
• On the influence of lookahead in competitive paging algorithms
• A unified analysis of paging and caching
• On-line file caching
• Competitive paging with locality of reference
• On adequate performance measures for paging
• The relative worst order ratio for online algorithms
• Beyond Competitive Analysis
• Markov Paging
• On-Line Paging Against Adversarially Biased Random Inputs
• The relative worst order ratio applied to seat reservation
• On the Relative Dominance of Paging Algorithms
• Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem
• List Update with Locality of Reference
• Algorithms – ESA 2004
• The working set model for program behavior
• On paging with locality of reference