The advice complexity of a class of hard online problems
DOI10.1007/s00224-016-9688-yzbMath1387.68302OpenAlexW1500425902MaRDI QIDQ1693995
Christian Kudahl, Jesper W. Mikkelsen, Joan. Boyar, Lene Monrad Favrholdt
Publication date: 1 February 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-016-9688-y
online algorithmsadvice complexitycomplexity classcovering designsasymmetric online covering (AOC)asymmetric string guessing
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Online algorithms; streaming algorithms (68W27)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online bin packing with advice
- On the advice complexity of online bipartite matching and online stable marriage
- 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 computation with advice
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Competitive snoopy caching
- Lower bounds for on-line graph coloring
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On-line vertex-covering
- Stochastic on-line knapsack problems
- Online independent sets.
- Advice complexity of maximum independent set in sparse and bipartite graphs
- The online knapsack problem: advice and randomization
- On Advice Complexity of the k-server Problem under Sparse Metrics
- Advice Complexity of Online Coloring for Paths
- On the Advice Complexity of the Set Cover Problem
- 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
- Optimal Online Edge Coloring of Planar Graphs with Advice
- On the Advice Complexity of the k-Server Problem
- The Online Set Cover Problem
- Information Complexity of Online Problems
- On the Advice Complexity of Online Problems
- Advice Complexity of the Online Coloring Problem
- Measuring the problem-relevant information in input
- Probability and Computing