Revisiting the COUNTER algorithms for list update

DOI10.1016/S0020-0190(97)00160-9MaRDI QIDQ287261zbMATH OpenFDO

Authors Susanne Albers, Michael Mitzenmacher

Publication date 26 May 2016

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

Full work available at URL https://doi.org/10.1016/S0020-0190(97)00160-9

zbMATH Keywords

data structureslist updateon-line algorithmsrandomized algorithms

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Recommendations

• Randomized competitive algorithms for the list update problem
• scientific article; zbMATH DE number 177552
• A new lower bound for the list update problem in the partial cost model
• The list update problem: Improved bounds for the counter scheme
• Two results on the list update problem

Cites work

• A combined BIT and TIMESTAMP algorithm for the list update problem
• A locally adaptive data compression scheme
• scientific article; zbMATH DE number 6472578 (Why is no real title available?)
• Off-line algorithms for the list update problem
• On the power of randomization in on-line algorithms
• Randomized competitive algorithms for the list update problem

Cited in

(6)

• A Survey of Algorithms and Models for List Update
• List update with probabilistic locality of reference
• List Update with Locality of Reference
• A new lower bound for the list update problem in the partial cost model
• A combined BIT and TIMESTAMP algorithm for the list update problem
• List update with delays or time windows

This page was built for publication: Revisiting the COUNTER algorithms for list update

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