Fractional Set Cover in the Streaming Model.

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

zbMATH Keywords

streaming algorithmsLP relaxationfractional set covermultiplicative weight update

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Beep-and-sleep: message and energy efficient set cover

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.