On the separation and equivalence of paging strategies and other online algorithms
From MaRDI portal
Publication:666671
DOI10.1007/s00453-018-0461-2zbMath1418.68246OpenAlexW2811044723MaRDI QIDQ666671
Alejandro López-Ortiz, Spyros Angelopoulos, Reza Dorrigiv
Publication date: 11 March 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0461-2
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On list update with locality of reference
- List update with probabilistic locality of reference
- A comparison of performance measures for online algorithms
- A theoretical comparison of LRU and LRU-K
- A combined BIT and TIMESTAMP algorithm for the list update problem
- On the relative dominance of paging algorithms
- The relative worst-order ratio applied to paging
- Online algorithms. The state of the art
- Two results on the list update problem
- LRU is better than FIFO
- Randomized competitive algorithms for the list update problem
- A new measure for the study of on-line algorithms
- On the influence of lookahead in competitive paging algorithms
- On algorithm design for metrical task systems
- A unified analysis of paging and caching
- Average case analyses of list update algorithms, with applications to data compression
- On the competitiveness of the move-to-front rule
- On-line file caching
- Competitive paging with locality of reference
- Stochastic dominance and the bijective ratio of online algorithms
- A comparison of performance measures via online search
- A simpler analysis of Burrows-Wheeler-based compression
- Relative interval analysis of paging algorithms on access graphs
- A Survey of Algorithms and Models for List Update
- Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
- On adequate performance measures for paging
- Optimal lower bounds for projective list update algorithms
- The relative worst order ratio for online algorithms
- An optimality proof of the LRU- K page replacement algorithm
- Online Priority Steiner Tree Problems
- Improved Randomized On-Line Algorithms for the List Update Problem
- Beyond Competitive Analysis
- Markov Paging
- On-Line Paging Against Adversarially Biased Random Inputs
- Strongly Competitive Algorithms for Paging with Locality of Reference
- The relative worst order ratio applied to seat reservation
- Paging and list update under bijective analysis
- List Update with Locality of Reference
- Algorithms – ESA 2004
- The working set model for program behavior
- On paging with locality of reference
- On the competitive theory and practice of online list accessing algorithms
