List Update with Locality of Reference

DOI10.1007/978-3-540-78773-0_35zbMath1136.68361OpenAlexW2138719999MaRDI QIDQ5458546

Spyros Angelopoulos, Reza Dorrigiv, Alejandro López-Ortiz

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_35

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Related Items

On list update with locality of reference, On the relative dominance of paging algorithms, List update with probabilistic locality of reference, List factoring and relative worst order analysis, Optimal strategies for the list update problem under the MRM alternative cost model, On the separation and equivalence of paging strategies and other online algorithms, Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis, Managing multiple mobile resources, Stochastic dominance and the bijective ratio of online algorithms, A Survey of Algorithms and Models for List Update, Parameterized analysis of paging and list update algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A combined BIT and TIMESTAMP algorithm for the list update problem
• Two results on the list update problem
• 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
• Average case analyses of list update algorithms, with applications to data compression
• On the competitiveness of the move-to-front rule
• Improved Randomized On-Line Algorithms for the List Update Problem
• A Simpler Analysis of Burrows-Wheeler Based Compression
• Algorithms – ESA 2004
• On paging with locality of reference