A Technique to Obtain Hardness Results for Randomized Online Algorithms

DOI10.1007/978-3-319-13350-8_20zbMath1323.68575OpenAlexW166732308MaRDI 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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (2)

Call admission problems on trees ⋮ Online bin covering with advice

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

This page was built for publication: A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey