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

DOI10.1007/978-3-319-13350-8_20MaRDI QIDQ2944895zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 15120 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• A Polylogarithmic-Competitive Algorithm for the k-Server Problem
• Advice complexity and barely random algorithms
• Advice complexity of online coloring for paths
• Advice complexity of the online coloring problem
• How Much Information about the Future Is Needed?
• Independent set with advice: the impact of graph knowledge (extended abstract)
• Information complexity of online problems
• Job shop scheduling with unit length tasks: bounds and algorithms
• Labelling Graphs with a Condition at Distance 2
• On advice complexity of the \(k\)-server problem under sparse metrics
• On online algorithms with advice for the \(k\)-server problem
• On the k -server conjecture
• On the Advice Complexity of Online Problems
• On the advice complexity of buffer management
• On the advice complexity of the \(k\)-server problem
• On the advice complexity of the knapsack problem
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• On the advice complexity of the set cover problem
• On the power of advice and randomization for the disjoint path allocation problem
• On the power of randomness versus advice in online computation
• Online Computation with Advice
• Online algorithms with advice for bin packing and scheduling problems
• Online bin packing with advice
• Online coloring of bipartite graphs with and without advice
• Online graph exploration with advice
• Online makespan scheduling with sublinear advice
• The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
• Tight bounds for the advice complexity of the online minimum Steiner tree problem
• Universal codeword sets and representations of the integers

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)