On the Power of Randomness versus Advice in Online Computation

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

Mathematics Subject Classification ID

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)

Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Unnamed Item ⋮ On the advice complexity of the \(k\)-server problem ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ Call admission problems on trees ⋮ The secretary problem with reservation costs ⋮ Online node- and edge-deletion problems with advice ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ Online Minimum Spanning Tree with Advice ⋮ On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles

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