arXiv preprint ·
Settling the Pass Complexity of Streaming Set Cover
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In the streaming set cover problem, $m$ sets from a universe of size $n$ are arriving one by one in a stream, and the algorithm is allowed to process the stream using one or a few passes and a space of $o(mn)$, which is sublinear in the input size. The goal is to determine the minimal (or approximately minimal) number of sets that cover the universe at the end of the last pass. This problem has been studied extensively over the years with rapid progress that led to several $O(\log{n})$-approximation algorithms in $\tilde{O}(mn^{1/p})$ space and $O(p)$ passes. However, progress on this front has largely stagnated over the past decade, despite the absence of any lower bounds that rule out even an $O(\log{n})$-approximation in $O(m)$ space and just two passes. We provide a simple explanation for this lack of progress by establishing an optimal three-way space-pass-approximation tradeoff for this problem: any $α$-approximation algorithm for streaming set cover requires $$ \widetildeΩ\Big(\frac{m}α \cdot \big(\frac{n}α\big)^{1/p}\Big) $$ space in $p$ passes whenever $α\ll n^{1/(p+1)}$. In light of prior work, this result is optimal up to constant factors in $p$ and logarithmic factors in $n,m$ for any $α\geq p$. Our bound is optimal with respect to the range of $α$ also, and fully settles the complexity of this fundamental problem in the streaming model. The proof of this result is (surprisingly) simple and non-technical and relies on a randomized reduction from a variant of the standard pointer chasing problem in communication complexity, using elementary properties of random sets.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Sparsification Framework for Directed Densest Subgraph
A Shortest Augmenting Path Algorithm for Linear Matroid Parity
Beyond odd characteristic: Faster isomorphism testing of 2-groups of Frattini class 2
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
A Faster Auction Algorithm for Weighted Matroid Intersection
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.