The advice complexity of a class of hard online problems
From MaRDI portal
Publication:1693995
Recommendations
Cites work
- 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?)
- 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
- 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 Problems
- On the advice complexity of online bipartite matching and online stable marriage
- 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
(30)- On the Advice Complexity of Online Edge- and Node-Deletion Problems
- On the advice complexity of the set cover problem
- 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
- Tight bounds for the advice complexity of the online minimum Steiner tree problem
- Advice complexity of the online induced subgraph problem
- On the power of advice and randomization for the disjoint path allocation problem
- The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
- Improved analysis of the online set cover problem with advice
- On the Advice Complexity of Online Problems
- Call admission problems on grids with advice
- Disjoint path allocation with sublinear advice
- Online node- and edge-deletion problems with advice
- Online minimum spanning trees with weight predictions
- Online interval scheduling with predictions
- Quantum online algorithms with respect to space and advice complexity
- Advice complexity for a class of online problems
- How Much Information about the Future Is Needed?
- Weighted Online Problems with Advice
- Advice complexity of online non-crossing matching
- Advice classes of parametrized tractability
- Weighted online problems with advice
- Independent set with advice: the impact of graph knowledge (extended abstract)
- Online Metric Algorithms with Untrusted Predictions
- Labeling schemes for deterministic radio multi-broadcast
- Call admission problems on trees
- Advice complexity of the online search problem
- On the advice complexity of the online dominating set problem
- A simple PTAS for the dual bin packing problem and advice complexity of its online version
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)
