Fractional Set Cover in the Streaming Model.
From MaRDI portal
Publication:5002615
DOI10.4230/LIPIcs.APPROX-RANDOM.2017.12zbMath1467.68222OpenAlexW2748190518MaRDI QIDQ5002615
Ronitt Rubinfeld, Anak Yodpinyanee, Sepideh Mahabadi, Ali Vakilian, Jonathan R. Ullman, Piotr Indyk
Publication date: 28 July 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.12
Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A nearly linear-time PTAS for explicit fractional packing and covering linear programs
- Computational experience with approximation algorithms for the set covering problem
- Nearly-Linear Time Positive LP Solver with Faster Convergence Rate
- Algorithmic construction of sets for k -restrictions
- Efficient Primal-Dual Graph Algorithms for MapReduce
- Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
- A threshold of ln n for approximating set cover
- The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
- Streaming Algorithms for Submodular Function Maximization
- A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
- On the hardness of approximating minimization problems
- Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Semi-Streaming Set Cover
- Analytical approach to parallel repetition
- Tight bounds for single-pass streaming complexity of the set cover problem
- Using Optimization to Break the Epsilon Barrier: A Faster and Simpler Width-Independent Algorithm for Solving Positive Linear Programs in Parallel
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
- STACS 2005
This page was built for publication: Fractional Set Cover in the Streaming Model.