A Survey of Algorithms and Models for List Update

DOI10.1007/978-3-642-40273-9_17MaRDI QIDQ2848979zbMATH OpenOpenAlexFDO

Authors Shahin Kamali, Alejandro Lopez-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)

Recommendations

• Analysis and experimentation on list update algorithms
• Off-line algorithms for the list update problem
• A new perspective on list update: probabilistic locality and working set
• Revisiting the COUNTER algorithms for list update
• Randomized competitive algorithms for the list update problem
• Improved Randomized On-Line Algorithms for the List Update Problem
• scientific article; zbMATH DE number 910898
• A competitive analysis of the list update problem with lookahead
• A competitive analysis of the list update problem with lookahead

Cites work

• A combined BIT and TIMESTAMP algorithm for the list update problem
• A locally adaptive data compression scheme
• A lower bound for randomized list update algorithms
• A new lower bound for the list update problem in the partial cost model
• A new measure for the study of on-line algorithms
• A unified analysis of paging and caching
• Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
• Algorithm Theory - SWAT 2004
• Algorithms – ESA 2004
• Average case analyses of list update algorithms, with applications to data compression
• Comparing online algorithms for bin packing problems
• Competitive paging with locality of reference
• scientific article; zbMATH DE number 1670645 (Why is no real title available?)
• scientific article; zbMATH DE number 1670671 (Why is no real title available?)
• scientific article; zbMATH DE number 1670833 (Why is no real title available?)
• scientific article; zbMATH DE number 432826 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1256656 (Why is no real title available?)
• scientific article; zbMATH DE number 6472578 (Why is no real title available?)
• Improved Randomized On-Line Algorithms for the List Update Problem
• List factoring and relative worst order analysis
• List Update with Locality of Reference
• LRU is better than FIFO
• Off-line algorithms for the list update problem
• On List Update with Locality of Reference
• On paging with locality of reference
• On self-organizing sequential search heuristics
• On Serial Files with Relocatable Records
• On the competitive theory and practice of online list accessing algorithms
• On the competitiveness of the move-to-front rule
• On the power of randomization in on-line algorithms
• On the separation and equivalence of paging strategies
• Online algorithms: a survey
• Online and Offline Access to Short Lists
• Optimal strategies for the list update problem under the MRM alternative cost model
• Paging and list update under bijective analysis
• Randomized competitive algorithms for the list update problem
• Separating online scheduling algorithms with the relative worst order ratio
• Strongly Competitive Algorithms for Paging with Locality of Reference
• The relative worst order ratio for online algorithms
• The relative worst-order ratio applied to paging
• The working set model for program behavior
• Two results on the list update problem

Cited in

(20)

• On lookahead in the list update problem
• Off-line algorithms for the list update problem
• Average case analyses of list update algorithms, with applications to data compression
• The itinerant list update problem
• On list update and work function algorithms.
• Paid exchanges are worth the price
• On list update with locality of reference
• scientific article; zbMATH DE number 1670645 (Why is no real title available?)
• Paid exchanges are worth the price
• On List Update with Locality of Reference
• List update with probabilistic locality of reference
• Optimal strategies for the list update problem under the MRM alternative cost model
• Improved Randomized On-Line Algorithms for the List Update Problem
• scientific article; zbMATH DE number 910898 (Why is no real title available?)
• Competitive Algorithms for Relaxed List Update and Multilevel Caching
• List Update with Locality of Reference
• Analysis and experimentation on list update algorithms
• Lossless image compression using list update algorithms
• On the separation and equivalence of paging strategies and other online algorithms
• A combined BIT and TIMESTAMP algorithm for the list update problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848979)