A Survey of Algorithms and Models for List Update

DOI10.1007/978-3-642-40273-9_17zbMath1395.68342OpenAlexW119445844MaRDI QIDQ2848979

Shahin Kamali, Alejandro López-Ortiz

Publication date: 13 September 2013

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

Full work available at URL: https://doi.org/10.1007/978-3-642-40273-9_17

Mathematics Subject Classification ID

Data structures (68P05) Online algorithms; streaming algorithms (68W27)

Related Items (3)

Paid exchanges are worth the price ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ On the list update problem with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal strategies for the list update problem under the MRM alternative cost model
• A combined BIT and TIMESTAMP algorithm for the list update problem
• A lower bound for randomized list update algorithms
• The relative worst-order ratio applied to paging
• Two results on the list update problem
• LRU is better than FIFO
• On the power of randomization in on-line algorithms
• Randomized competitive algorithms for the list update problem
• A new measure for the study of on-line algorithms
• Off-line algorithms for the list update problem
• A unified analysis of paging and caching
• Average case analyses of list update algorithms, with applications to data compression
• Online algorithms: a survey
• On the competitiveness of the move-to-front rule
• Competitive paging with locality of reference
• List factoring and relative worst order analysis
• Separating online scheduling algorithms with the relative worst order ratio
• Comparing online algorithms for bin packing problems
• Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
• The relative worst order ratio for online algorithms
• On List Update with Locality of Reference
• Online and Offline Access to Short Lists
• A locally adaptive data compression scheme
• On self-organizing sequential search heuristics
• Improved Randomized On-Line Algorithms for the List Update Problem
• Strongly Competitive Algorithms for Paging with Locality of Reference
• Algorithm Theory - SWAT 2004
• On Serial Files with Relocatable Records
• 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
• A new lower bound for the list update problem in the partial cost model

This page was built for publication: A Survey of Algorithms and Models for List Update