Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis

DOI10.1007/978-3-540-77891-2_2zbMath1132.68825MaRDI QIDQ5452148

Alejandro López-Ortiz, Reza Dorrigiv

Publication date: 25 March 2008

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77891-2_2

Mathematics Subject Classification ID

68W40: Analysis of algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• LRU is better than FIFO
• Randomized competitive algorithms for the list update problem
• A new measure for the study of on-line algorithms
• A unified analysis of paging and caching
• On-line file caching
• Competitive paging with locality of reference
• The seat reservation problem
• The Accommodating Function: A Generalization of the Competitive Ratio
• On adequate performance measures for paging
• Cache-Oblivious Algorithms
• Beyond Competitive Analysis
• Markov Paging
• On-Line Paging Against Adversarially Biased Random Inputs
• Strongly Competitive Algorithms for Paging with Locality of Reference
• Algorithm Theory - SWAT 2004
• On the Relative Dominance of Paging Algorithms
• On Certain New Models for Paging with Locality of Reference
• List Update with Locality of Reference
• Algorithms – ESA 2004
• The working set model for program behavior
• On paging with locality of reference