A new lower bound for the list update problem in the partial cost model

DOI10.1016/S0304-3975(00)00257-7zbMath0984.68193OpenAlexW1976036725MaRDI QIDQ5958711

Bernhard von Stengel, Bernd Gärtner, Christoph Ambühl

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00257-7

zbMATH Keywords

competitive analysisanalysis of algorithmson-line algorithmslist-update

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

On list update with locality of reference ⋮ A Survey of Algorithms and Models for List Update

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A combined BIT and TIMESTAMP algorithm for the list update problem
• A lower bound for randomized list update algorithms
• Online algorithms. The state of the art
• Two results on the list update problem
• On the power of randomization in on-line algorithms
• Randomized competitive algorithms for the list update problem
• Off-line algorithms for the list update problem
• Efficient computation of behavior strategies
• Fast algorithms for finding randomized strategies in game trees
• An optimal on-line algorithm for metrical task system

This page was built for publication: A new lower bound for the list update problem in the partial cost model