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

zbMATH Keywords

online algorithmsadvice complexitycomplexity classcovering designsasymmetric online covering (AOC)asymmetric string guessing

Mathematics Subject Classification ID

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

Call admission problems on grids with advice, Labeling schemes for deterministic radio multi-broadcast, Call admission problems on trees, Online Metric Algorithms with Untrusted Predictions, Online minimum spanning trees with weight predictions, Online interval scheduling with predictions, Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems, Online knapsack with removal and recourse, A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version, Quantum online algorithms with respect to space and advice complexity, On the advice complexity of the online dominating set problem, On conceptually simple algorithms for variants of online bipartite matching, Weighted online problems with advice

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