On the relative dominance of paging algorithms

DOI10.1016/j.tcs.2009.04.023zbMath1171.68046OpenAlexW2093015753MaRDI 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

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05)

Related Items

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

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