Improved analysis of the online set cover problem with advice
From MaRDI portal
Publication:2402263
DOI10.1016/j.tcs.2017.05.029zbMath1372.68309MaRDI QIDQ2402263
Jeff Edmonds, Sacha Krug, Richard Královič, Tobias Mömke, Dennis Komm, Stefan Dobrev, Rastislav Královič
Publication date: 7 September 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.05.029
Related Items
Unnamed Item, Fully Online Matching with Advice on General Bipartite Graphs and Paths, The \(k\)-server problem with advice in \(d\) dimensions and on the sphere
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online computation with advice
- Online algorithms. The state of the art
- On the power of randomization in on-line algorithms
- Online algorithms: a survey
- Weighted sums of certain dependent random variables
- Towards polynomial lower bounds for dynamic problems
- On the Advice Complexity of the Knapsack Problem
- On the Advice Complexity of the Set Cover Problem
- 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
- Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
- The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
- Advice Complexity and Barely Random Algorithms
- Measuring the problem-relevant information in input
- Probability Inequalities for Sums of Bounded Random Variables
- How Much Information about the Future Is Needed?
- Probability and Computing
