A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey
From MaRDI portal
Publication:2944895
DOI10.1007/978-3-319-13350-8_20zbMath1323.68575MaRDI QIDQ2944895
Juraj Hromkovič, Dennis Komm, Hans-Joachim Böckenhauer
Publication date: 8 September 2015
Published in: Computing with New Resources (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/20.500.11850/182208
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20: Randomized algorithms
68W27: Online algorithms; streaming algorithms
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online algorithms with advice for bin packing and scheduling problems
- On the list update problem with advice
- Independent Set with Advice: The Impact of Graph Knowledge
- On Advice Complexity of the k-server Problem under Sparse Metrics
- Advice Complexity of Online Coloring for Paths
- On the Advice Complexity of the Knapsack Problem
- On Online Algorithms with Advice for the k-Server Problem
- On the Advice Complexity of the Set Cover Problem
- Online Graph Exploration with Advice
- Online Coloring of Bipartite Graphs with and without Advice
- Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem
- On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
- On the Advice Complexity of the k-Server Problem
- On the Power of Randomness versus Advice in Online Computation
- Information Complexity of Online Problems
- Online Computation with Advice
- On the Advice Complexity of Online Problems
- Labelling Graphs with a Condition at Distance 2
- Universal codeword sets and representations of the integers
- On the k -server conjecture
- On the Advice Complexity of Buffer Management
- Advice Complexity of the Online Coloring Problem
- On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles
- The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
- Online Makespan Scheduling with Sublinear Advice
- Advice Complexity and Barely Random Algorithms
- How Much Information about the Future Is Needed?
- A Polylogarithmic-Competitive Algorithm for the k-Server Problem
