The advice complexity of a class of hard online problems
From MaRDI portal
Recommendations
Cites work
- Advice complexity of maximum independent set in sparse and bipartite graphs
- Advice complexity of online coloring for paths
- Advice complexity of the online coloring problem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Competitive snoopy caching
- scientific article; zbMATH DE number 53885 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- Information complexity of online problems
- Lower bounds for on-line graph coloring
- Measuring the problem-relevant information in input
- On advice complexity of the k-server problem under sparse metrics
- On the advice complexity of online bipartite matching and online stable marriage
- On the Advice Complexity of Online Problems
- On the advice complexity of the k-server problem
- On the advice complexity of the set cover problem
- On the power of advice and randomization for the disjoint path allocation problem
- On-line vertex-covering
- Online algorithms with advice for bin packing and scheduling problems
- Online bin packing with advice
- Online coloring of bipartite graphs with and without advice
- Online computation with advice
- Online independent sets.
- Optimal online edge coloring of planar graphs with advice
- Probability and Computing
- Stochastic on-line knapsack problems
- The online knapsack problem: advice and randomization
- The online set cover problem
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Tight bounds for the advice complexity of the online minimum Steiner tree problem
Cited in
(35)- Online node- and edge-deletion problems with advice
- On the advice complexity of the online dominating set problem
- Call admission problems on grids with advice
- Improved analysis of the online set cover problem with advice
- Labeling schemes for deterministic radio multi-broadcast
- Call admission problems on trees
- Advice complexity of online non-crossing matching
- Weighted Online Problems with Advice
- Advice complexity of the online search problem
- Independent set with advice: the impact of graph knowledge (extended abstract)
- 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
- Advice complexity of disjoint path allocation
- Advice complexity for a class of online problems
- Disjoint path allocation with sublinear advice
- On the Advice Complexity of Online Problems
- Advice complexity of the online induced subgraph problem
- The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
- A simple PTAS for the dual bin packing problem and advice complexity of its online version
- How Much Information about the Future Is Needed?
- Online Metric Algorithms with Untrusted Predictions
- On the Advice Complexity of Online Edge- and Node-Deletion Problems
- 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
- Quantum online algorithms with respect to space and advice complexity
- Advice classes of parametrized tractability
- Complexity classes for online problems with and without predictions
- Comparing the hardness of online minimization and maximization problems with predictions
- Online unbounded knapsack
- Weighted online problems with advice
- Online interval scheduling with predictions
- Complexity classes for online problems with and without predictions
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)
