Tight bounds for single-pass streaming complexity of the set cover problem

DOI10.1145/2897518.2897576MaRDI QIDQ5361872zbMATH OpenOpenAlexFDO

Authors Sepehr Assadi, Sanjeev Khanna, Yang Li

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.05715

zbMATH Keywords

communication complexitycovering integer programsset coverstreaming algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Abstract: We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $alpha$-approximate set cover (for any $alpha=o(sqrtn)$) using a single-pass streaming algorithm, we show that $Theta(mn/alpha)$ space is both sufficient and necessary (up to an $O(logn)$ factor); here $m$ denotes number of the sets and $n$ denotes size of the universe. This provides a strong negative answer to the open question posed by Indyk et al. (2015) regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sub-linear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets), and establish that an additional factor of $alpha$ saving in the space is achievable in this case and that this is the best possible. In other words, we show that $Theta(mn/alph{a}^2)$ space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of $alpha$. Our algorithm in fact works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances where the sets are presented in a random order.

Recommendations

• Tight bounds for single-pass streaming complexity of the set cover problem
• Incidence geometries and the pass complexity of semi-streaming set cover
• Semi-streaming set cover
• Semi-streaming set cover (extended abstract)
• scientific article; zbMATH DE number 6905172

Cited in

(20)

• Fixed parameter tractability of graph deletion problems over data streams
• Online algorithms for the maximum \(k\)-interval coverage problem
• Tight bounds on subexponential time approximation of set cover and related problems
• Better streaming algorithms for the maximum coverage problem
• Graph sketching and streaming: new approaches for analyzing massive graphs
• Incidence geometries and the pass complexity of semi-streaming set cover
• Set cover in sub-linear time
• Semi-streaming set cover
• Tight bounds for single-pass streaming complexity of the set cover problem
• Fractional set cover in the streaming model
• Semi-streaming set cover (extended abstract)
• Approximate F₂-Sketching of Valuation Functions
• Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
• Stochastic minimum vertex cover in general graphs: a 3/2-approximation
• Fair maximization of monotone submodular functions in data streams
• Maximum coverage in the data stream model: parameterized and generalized
• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• Improved algorithms for maximum coverage in dynamic and random order streams
• Streaming submodular maximization with fairness constraints for massive data summarization
• Almost optimal superconstant-pass streaming lower bounds for reachability

This page was built for publication: Tight bounds for single-pass streaming complexity of the set cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361872)