Advice Complexity and Barely Random Algorithms

DOI10.1051/ita/2011105zbMath1218.68090OpenAlexW2013227361MaRDI QIDQ5198936

Richard Královič, Dennis Komm

Publication date: 10 August 2011

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/222011

zbMATH Keywords

information contentadvice complexityonline problemsbarely random algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Randomized algorithms (68W20)

Related Items (23)

On the Power of Randomness versus Advice in Online Computation ⋮ Online Bin Packing with Advice of Small Size ⋮ Online Multi-Coloring with Advice ⋮ Job shop scheduling with unit length tasks ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Disjoint Path Allocation with Sublinear Advice ⋮ On the advice complexity of the \(k\)-server problem ⋮ Improved analysis of the online set cover problem with advice ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ Reordering buffer management with advice ⋮ The online knapsack problem: advice and randomization ⋮ Online coloring of bipartite graphs with and without advice ⋮ Online algorithms with advice for bin packing and scheduling problems ⋮ The \(k\)-server problem with advice in \(d\) dimensions and on the sphere ⋮ On the list update problem with advice ⋮ Online algorithms with advice: the tape model ⋮ Online Minimum Spanning Tree with Advice ⋮ Advice Complexity and Barely Random Algorithms ⋮ The string guessing problem as a method to prove lower bounds on the advice complexity ⋮ Advice Complexity of the Online Search Problem ⋮ Online bin packing with advice of small size ⋮ Online multi-coloring with advice ⋮ Online bin packing with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Online algorithms with advice: the tape model
• Online computation with advice
• An efficient algorithm for the job-shop problem with two jobs
• Randomized competitive algorithms for the list update problem
• Competitive analysis of randomized paging algorithms
• Advice Complexity and Barely Random Algorithms
• Information Complexity of Online Problems
• On the power of randomization for job shop scheduling withk-units length tasks
• On the Advice Complexity of Online Problems
• How Much Information about the Future Is Needed?

This page was built for publication: Advice Complexity and Barely Random Algorithms