A lower bound for randomized list update algorithms

DOI10.1016/0020-0190(93)90150-8zbMath0794.68070OpenAlexW2006254254MaRDI QIDQ685486

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

lower boundsrandomized algorithmslist update algorithms

Mathematics Subject Classification ID

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

Related Items (11)

The list update problem and the retrieval of sets ⋮ Off-line algorithms for the list update problem ⋮ A competitive analysis of the list update problem with lookahead ⋮ Self-adjusting grid networks ⋮ Relative Worst-Order Analysis: A Survey ⋮ List factoring and relative worst order analysis ⋮ A combined BIT and TIMESTAMP algorithm for the list update problem ⋮ A new lower bound for the list update problem in the partial cost model ⋮ Equilibria in Online Games ⋮ A Survey of Algorithms and Models for List Update ⋮ On list update and work function algorithms.

Cites Work

• Two results on the list update problem
• Unnamed Item

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