A combined BIT and TIMESTAMP algorithm for the list update problem

DOI10.1016/0020-0190(95)00142-YzbMATH Open0875.68392OpenAlexW1989791077MaRDI QIDQ672254FDOQ672254

Authors: Susanne Albers, Bernhard von Stengel, Ralph Werchner 

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

Recommendations

• Off-line algorithms for the list update problem
• The list update problem: Improved bounds for the counter scheme
• Revisiting the COUNTER algorithms for list update
• A Survey of Algorithms and Models for List Update
• Improved Randomized On-Line Algorithms for the List Update Problem
• scientific article; zbMATH DE number 910898
• Randomized competitive algorithms for the list update problem
• A New Timestamping Scheme Based on Skip Lists
• A lower bound for randomized list update algorithms
• scientific article; zbMATH DE number 177552

zbMATH Keywords

Analysis of algorithmsCompetitive analysisList-updateOn-line algorithms

Mathematics Subject Classification ID

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

Cites Work

• On the power of randomization in on-line algorithms
• Two results on the list update problem
• Randomized competitive algorithms for the list update problem
• Title not available (Why is that?)
• A lower bound for randomized list update algorithms

Cited In (21)

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

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

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