Optimal lower bounds for projective list update algorithms

DOI10.1145/2500120zbMath1301.68138arXiv1002.2440OpenAlexW2046103177MaRDI QIDQ2933662

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

Publication date: 5 December 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1002.2440

zbMATH Keywords

competitive analysisonline algorithmslinear lists

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

Related Items (2)

On the separation and equivalence of paging strategies and other online algorithms ⋮ On the list update problem with advice

This page was built for publication: Optimal lower bounds for projective list update algorithms