Advice Complexity and Barely Random Algorithms

DOI10.1051/ita/2011105zbMath1218.68090MaRDI 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 content; advice complexity; online problems; barely random algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

68W20: Randomized algorithms

Related Items

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