Entropy-based bounds for online algorithms

DOI10.1145/1186810.1186817zbMath1321.68517OpenAlexW2073523085MaRDI QIDQ2944543

Eli Upfal, Gopal Pandurangan

Publication date: 2 September 2015

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

Full work available at URL: https://doi.org/10.1145/1186810.1186817

zbMATH Keywords

entropystochastic processonline algorithmsprefetchingcachingperformance boundslist accessing

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)

This page was built for publication: Entropy-based bounds for online algorithms