Measuring the problem-relevant information in input

DOI10.1051/ita/2009012zbMath1176.68089MaRDI QIDQ5321779

Stefan Dobrev, Rastislav Královič, Dana Pardubská

Publication date: 15 July 2009

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2009__43_3_585_0/

zbMATH Keywords

online algorithms; communication complexity; paging; advice complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)