On the Power of Randomness versus Advice in Online Computation
From MaRDI portal
Publication:3166941
DOI10.1007/978-3-642-31644-9_2zbMath1367.68340MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20: Randomized algorithms
68W27: Online algorithms; streaming algorithms
Related Items
Online Minimum Spanning Tree with Advice, On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere, Online node- and edge-deletion problems with advice, Two-way and one-way quantum and classical automata with advice for online minimization problems, On the advice complexity of the \(k\)-server problem, Call admission problems on trees, The secretary problem with reservation costs, A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey, Unnamed Item
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?
