A lower bound for randomized list update algorithms

DOI10.1016/0020-0190(93)90150-8zbMATH Open0794.68070OpenAlexW2006254254MaRDI QIDQ685486FDOQ685486

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

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

zbMATH Keywords

randomized algorithmslower boundslist update algorithms

Mathematics Subject Classification ID

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

Cites Work

• Two results on the list update problem
• Title not available (Why is that?)

Cited In (21)

• On list update and work function algorithms.
• A competitive analysis of the list update problem with lookahead
• A new family of randomized algorithms for list accessing
• Improved Randomized On-Line Algorithms for the List Update Problem
• Self-adjusting linear networks
• A combined BIT and TIMESTAMP algorithm for the list update problem
• Title not available (Why is that?)
• A new lower bound for the list update problem in the partial cost model
• Self-adjusting grid networks
• Verified analysis of list update algorithms
• The weighted list update problem and the lazy adversary
• Randomized competitive algorithms for the list update problem
• Average case analyses of list update algorithms, with applications to data compression
• Optimal lower bounds for projective list update algorithms
• Off-line algorithms for the list update problem
• Relative Worst-Order Analysis: A Survey
• A guessing game and randomized online algorithms
• List factoring and relative worst order analysis
• A Survey of Algorithms and Models for List Update
• Equilibria in online games
• The list update problem and the retrieval of sets

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)