The advice complexity of a class of hard online problems
DOI10.1007/S00224-016-9688-YzbMATH Open1387.68302OpenAlexW1500425902MaRDI QIDQ1693995FDOQ1693995
Authors: Christian Kudahl, Jesper W. Mikkelsen, Joan Boyar, Lene M. 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
Recommendations
online algorithmsadvice complexitycomplexity classcovering designsasymmetric online covering (AOC)asymmetric string guessing
Online algorithms; streaming algorithms (68W27) 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)
Cites Work
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Stochastic on-line knapsack problems
- The online knapsack problem: advice and randomization
- Online bin packing with advice
- Advice complexity of online coloring for paths
- On the advice complexity of the set cover problem
- On the advice complexity of the \(k\)-server problem
- Information complexity of online problems
- On the Advice Complexity of Online Problems
- Title not available (Why is that?)
- Online coloring of bipartite graphs with and without advice
- Advice complexity of the online coloring problem
- Online algorithms with advice for bin packing and scheduling problems
- On the list update problem with advice
- Measuring the problem-relevant information in input
- Online computation with advice
- Probability and Computing
- Competitive snoopy caching
- The online set cover problem
- Title not available (Why is that?)
- Online independent sets.
- Title not available (Why is that?)
- Lower bounds for on-line graph coloring
- On advice complexity of the \(k\)-server problem under sparse metrics
- On the advice complexity of online bipartite matching and online stable marriage
- On-line vertex-covering
- The string guessing problem as a method to prove lower bounds on the advice complexity
- On the power of advice and randomization for the disjoint path allocation problem
- Advice complexity of maximum independent set in sparse and bipartite graphs
- Tight bounds for the advice complexity of the online minimum Steiner tree problem
- Optimal online edge coloring of planar graphs with advice
Cited In (31)
- On the advice complexity of the online dominating set problem
- On the power of advice and randomization for the disjoint path allocation problem
- Disjoint path allocation with sublinear advice
- Advice complexity for a class of online problems
- Weighted online problems with advice
- Online Metric Algorithms with Untrusted Predictions
- Call admission problems on grids with advice
- Independent set with advice: the impact of graph knowledge (extended abstract)
- On the advice complexity of the set cover problem
- The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
- Online minimum spanning trees with weight predictions
- Online interval scheduling with predictions
- Weighted Online Problems with Advice
- Advice classes of parametrized tractability
- A simple PTAS for the dual bin packing problem and advice complexity of its online version
- Advice complexity bounds for online delayed \(\mathcal{F} \)-node-, \(H\)-node- and \(H\)-edge-deletion problems
- Online knapsack with removal and recourse
- Advice complexity of disjoint path allocation
- Advice complexity of the online induced subgraph problem
- Improved analysis of the online set cover problem with advice
- How Much Information about the Future Is Needed?
- Labeling schemes for deterministic radio multi-broadcast
- Call admission problems on trees
- Advice complexity of online non-crossing matching
- On the Advice Complexity of Online Edge- and Node-Deletion Problems
- On the Advice Complexity of Online Problems
- Tight bounds for the advice complexity of the online minimum Steiner tree problem
- Quantum online algorithms with respect to space and advice complexity
- Online node- and edge-deletion problems with advice
- On conceptually simple algorithms for variants of online bipartite matching
- Advice complexity of the online search problem
This page was built for publication: The advice complexity of a class of hard online problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1693995)
