A combined BIT and TIMESTAMP algorithm for the list update problem

DOI10.1016/0020-0190(95)00142-YzbMath0875.68392OpenAlexW1989791077MaRDI QIDQ672254

Ralph Werchner, Bernhard von Stengel, Susanne Albers

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00142-y

zbMATH Keywords

Competitive analysisOn-line algorithmsAnalysis of algorithmsList-update

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of data (68P99)

Related Items (17)

On list update with locality of reference ⋮ Revisiting the COUNTER algorithms for list update ⋮ A competitive analysis of the list update problem with lookahead ⋮ Paid exchanges are worth the price ⋮ Self-adjusting grid networks ⋮ Relative Worst-Order Analysis: A Survey ⋮ List factoring and relative worst order analysis ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ On the list update problem with advice ⋮ A new lower bound for the list update problem in the partial cost model ⋮ List Update with Locality of Reference ⋮ Randomized distributed online algorithms against adaptive offline adversaries ⋮ A Survey of Algorithms and Models for List Update ⋮ On-line and off-line preemptive two-machine job shop scheduling ⋮ On list update and work function algorithms. ⋮ A randomized algorithm for two servers on the line. ⋮ Delayed information and action in on-line algorithms

Cites Work

• Unnamed Item
• A lower bound for randomized list update algorithms
• Two results on the list update problem
• On the power of randomization in on-line algorithms
• Randomized competitive algorithms for the list update problem

This page was built for publication: A combined BIT and TIMESTAMP algorithm for the list update problem