Two results on the list update problem

DOI10.1016/0020-0190(91)90086-WMaRDI QIDQ1178243zbMATH OpenFDO

Authors Sandy Irani

Publication date 26 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90086-W

zbMATH Keywords

amortized analysiscompetitive analysislinear listsrandomized on- line algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• 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 lower bound for randomized list update algorithms

Cited in

(39)

• A competitive analysis of the list update problem with lookahead
• The weighted list update problem and the lazy adversary
• Randomized competitive algorithms for the list update problem
• On lookahead in the list update problem
• The list update problem and the retrieval of sets
• A parallel list update problem
• Off-line algorithms for the list update problem
• On the competitiveness of the move-to-front rule
• On list update and work function algorithms.
• New results for online page replication
• List factoring and relative worst order analysis
• Paid exchanges are worth the price
• Can Burrows-Wheeler transform be replaced in chain code compression?
• On list update with locality of reference
• scientific article; zbMATH DE number 1670833 (Why is no real title available?)
• A Survey of Algorithms and Models for List Update
• Revisiting the COUNTER algorithms for list update
• Optimal lower bounds for projective list update algorithms
• Paid exchanges are worth the price
• A randomized algorithm for online scheduling with interval conflicts
• scientific article; zbMATH DE number 4092762 (Why is no real title available?)
• scientific article; zbMATH DE number 177552 (Why is no real title available?)
• scientific article; zbMATH DE number 1303545 (Why is no real title available?)
• List update with probabilistic locality of reference
• Verified analysis of list update algorithms
• Competitive Algorithms for Relaxed List Update and Multilevel Caching
• The list update problem and the retrieval of sets
• List Update 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
• Analysis and experimentation on list update algorithms
• Relative Worst-Order Analysis: A Survey
• Online computation with untrusted advice
• On the separation and equivalence of paging strategies and other online algorithms
• A combined BIT and TIMESTAMP algorithm for the list update problem
• A lower bound for randomized list update algorithms
• List update with delays or time windows
• A 3.3904-competitive online algorithm for list update with uniform costs
• Randomized distributed online algorithms against adaptive offline adversaries

This page was built for publication: Two results on the list update problem

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