A lower bound for randomized list update algorithms

DOI10.1016/0020-0190(93)90150-8MaRDI QIDQ685486zbMATH OpenOpenAlexFDO

Authors Boris Teia

Publication date 17 October 1993

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

Full work available at URL https://doi.org/10.1016/0020-0190(93)90150-8

zbMATH Keywords

list update algorithmslower boundsrandomized algorithms

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Review text

The author deals with randomized online algorithms for a static list update problem. As a main result it is shown that 1.5 competitiveness presents a lower bound for such algorithms, i.e., the expected cost of any sequence of requests is no more than 1.5 times the cost of an optimal off-line algorithm. The original research is combined with an older result of \textit{A. C. Yao} [Probabilistic computations: Towards a unified measure of complexity, Proc. 18th. Symp. on Foundation of Computer Science, 222-227 (1977)].

Recommendations

• Randomized competitive algorithms for the list update problem
• The list update problem: Improved bounds for the counter scheme
• Improved Randomized On-Line Algorithms for the List Update Problem
• scientific article; zbMATH DE number 910898
• Optimal lower bounds for projective list update algorithms
• A new lower bound for the list update problem in the partial cost model
• A new family of randomized algorithms for list accessing
• Off-line algorithms for the list update problem
• scientific article; zbMATH DE number 1775407
• Lower time bounds for randomized computation

Cites work

• scientific article; zbMATH DE number 432826 (Why is no real title available?)
• Two results on the list update problem

Cited in

(24)

• A competitive analysis of the list update problem with lookahead
• Two results on the list update problem
• The weighted list update problem and the lazy adversary
• Randomized competitive algorithms for the list update problem
• The list update problem and the retrieval of sets
• Off-line algorithms for the list update problem
• Average case analyses of list update algorithms, with applications to data compression
• On list update and work function algorithms.
• List factoring and relative worst order analysis
• Equilibria in online games
• A Survey of Algorithms and Models for List Update
• Optimal lower bounds for projective list update algorithms
• A guessing game and randomized online algorithms
• Improved Randomized On-Line Algorithms for the List Update Problem
• Verified analysis of list update algorithms
• scientific article; zbMATH DE number 910898 (Why is no real title available?)
• A new lower bound for the list update problem in the partial cost model
• Self-adjusting grid networks
• Relative Worst-Order Analysis: A Survey
• Self-adjusting linear networks
• A combined BIT and TIMESTAMP algorithm for the list update problem
• List update with delays or time windows
• A 3.3904-competitive online algorithm for list update with uniform costs
• A new family of randomized algorithms for list accessing

This page was built for publication: A lower bound for randomized list update algorithms

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