On the Power of Randomness versus Advice in Online Computation
Publication:3166941
DOI10.1007/978-3-642-31644-9_2zbMath1367.68340OpenAlexW19276351MaRDI QIDQ3166941
Dennis Komm, Richard Královič, Juraj Hromkovič, Peter Rossmanith, Hans-Joachim Böckenhauer
Publication date: 1 November 2012
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/20.500.11850/182154
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (10)
Cites Work
- Unnamed Item
- Online computation with advice
- Online algorithms. The state of the art
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- On the Advice Complexity of the k-Server Problem
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- Advice Complexity and Barely Random Algorithms
- Measuring the problem-relevant information in input
- How Much Information about the Future Is Needed?
This page was built for publication: On the Power of Randomness versus Advice in Online Computation