A technique to obtain hardness results for randomized online algorithms -- a survey

DOI10.1007/978-3-319-13350-8_20zbMATH Open1323.68575OpenAlexW166732308MaRDI QIDQ2944895FDOQ2944895

Authors: 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

Recommendations

Randomization can be as helpful as a glimpse of the future in online computation
Online algorithms with advice: the tape model
On the power of randomness versus advice in online computation
On the Advice Complexity of Online Problems
Advice complexity and barely random algorithms

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

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
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
On the advice complexity of the \(k\)-server problem
Information complexity of online problems
On the Advice Complexity of Online Problems
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 (extended abstract)
Online algorithms with advice for bin packing and scheduling problems
Advice complexity and barely random algorithms
Labelling Graphs with a Condition at Distance 2
Universal codeword sets and representations of the integers
On the k -server conjecture
Independent set with advice: the impact of graph knowledge (extended abstract)
On advice complexity of the \(k\)-server problem under sparse metrics
Online Computation with Advice
On the advice complexity of buffer management
How Much Information about the Future Is Needed?
Online bin packing with advice
Title not available (Why is that?)
Online makespan scheduling with sublinear advice
On the power of advice and randomization for the disjoint path allocation problem
Job shop scheduling with unit length tasks: bounds and algorithms
On the power of randomness versus advice in online computation
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Tight bounds for the advice complexity of the online minimum Steiner tree problem

Cited In (4)

Randomized Online Algorithms with High Probability Guarantees
Online bin covering with advice
Call admission problems on trees
On the power of randomness versus advice in online computation

This page was built for publication: A technique to obtain hardness results for randomized online algorithms -- a survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944895)