# Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

@article{Chakrabarti2015IncidenceGA, title={Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover}, author={Amit Chakrabarti and Anthony Wirth}, journal={Electron. Colloquium Comput. Complex.}, year={2015}, volume={22}, pages={113} }

Set cover, over a universe of size n, may be modelled as a data-streaming problem, where the m sets that comprise the instance are to be read one by one. A semi-streaming algorithm is allowed only O(npoly{log n, log m}) space to process this stream. For each p ≤ 1, we give a very simple deterministic algorithm that makes p passes over the input stream and returns an appropriately certified (p + 1)n1/(p + 1)-approximation to the optimum set cover. More importantly, we proceed to show that this… Expand

#### Topics from this paper

#### 33 Citations

Towards Tight Bounds for the Streaming Set Cover Problem

- Computer Science, Mathematics
- PODS
- 2016

This work considers the classic Set Cover problem in the data stream model and shows that any algorithm that computes set cover exactly using ({1 over 2δ}-1) passes must use ~Ω(mnδ) space in the regime of m=O(n). Expand

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

- Mathematics, Computer Science
- STOC
- 2016

The space complexity of single-pass streaming algorithms for approximating the classic set cover problem is resolved, and it is shown that Θ(mn/α2) space is both sufficient and necessary for estimating the size of a minimum set cover to within a factor of α. Expand

Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem

- Computer Science, Mathematics
- PODS
- 2017

This work shows that any α-approximation algorithm for the set cover problem requires Ω(mn1/α) space, even if it is allowed polylog(n) passes over the stream, and even if the sets are arriving in a random order in the stream. Expand

Semi-Streaming Set Cover

- Computer Science, Mathematics
- ACM Trans. Algorithms
- 2016

A semi-streaming algorithm is designed that on input hypergraph G constructs a succinct data structure D such that for every 0 ⩽ ε < 1, an edge (1 − ε)-cover that approximates the optimal edge ( 1-)cover within a factor of f(ε, n) can be extracted from D (efficiently and with no additional space requirements). Expand

Set Cover in Sub-linear Time

- Mathematics, Computer Science
- SODA
- 2018

This work involves a probabilistic construction of a certain set system with a minimum set cover of size αk, with the key property that a small number of "almost uniformly distributed" modifications can reduce theminimum set cover size down to k. Expand

Better Streaming Algorithms for the Maximum Coverage Problem

- Computer Science, Mathematics
- Theory of Computing Systems
- 2018

The main goal of this work is to design algorithms, with approximation guarantees as close as possible to 1−1/e$1-1/ e$, that use sublinear space o(mn)$o(mn), and to study the maximum k-vertex coverage problem in the dynamic graph stream model. Expand

Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model

- Mathematics, Computer Science
- PODS
- 2019

A single-pass algorithm is designed that reports an α-approximate solution in $\tildeO (m/α^2 + k)$ space and heavily exploits data stream sketching techniques, which could lead to further connections between vector sketching methods and streaming algorithms for combinatorial optimization tasks. Expand

Fractional Set Cover in the Streaming Model

- Mathematics, Computer Science
- APPROX-RANDOM
- 2017

A randomized (1+a)-approximation algorithm that makes p passes over the data, and uses O(polylog(m,n,1/a) (mn^(O(1/(pa)))+n)) memory space, which is the first streaming result for the fractional set cover problem. Expand

Maximum Coverage in the Data Stream Model: Parameterized and Generalized

- Computer Science
- ICDT
- 2021

The goal is to design single-pass algorithms that use space that is sublinear in the input size of the data stream model and obtain an algorithm for the parameterized version of the streaming SetCover problem. Expand

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs

- Computer Science
- ICALP
- 2021

The space complexity of this random walk simulation problem for two-pass streaming algorithms is essentially settled, showing that it is Θ̃(n · √ L), by giving almost matching upper and lower bounds. Expand

#### References

SHOWING 1-10 OF 36 REFERENCES

Semi-Streaming Set Cover

- Computer Science, Mathematics
- ACM Trans. Algorithms
- 2016

A semi-streaming algorithm is designed that on input hypergraph G constructs a succinct data structure D such that for every 0 ⩽ ε < 1, an edge (1 − ε)-cover that approximates the optimal edge ( 1-)cover within a factor of f(ε, n) can be extracted from D (efficiently and with no additional space requirements). Expand

On Streaming and Communication Complexity of the Set Cover Problem

- Mathematics, Computer Science
- DISC
- 2014

We develop the first streaming algorithm and the first two-party communication protocol that uses a constant number of passes/rounds and sublinear space/communication for logarithmic approximation to… Expand

On graph problems in a semi-streaming model

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2005

In the course of this general study, semi-streaming constant approximation algorithms for the unweighted and weighted matching problems are given, along with a further algorithmic improvement for the bipartite case. Expand

Recognizing well-parenthesized expressions in the streaming model

- Computer Science, Mathematics
- STOC '10
- 2010

It is proved that this one-pass algorithm for Dyck(2) is optimal, up to a log(n) factor, even when two-sided error is allowed, and conjecture that a similar bound holds for any constant number of passes over the input. Expand

A threshold of ln n for approximating set cover (preliminary version)

- Mathematics, Computer Science
- STOC '96
- 1996

We prove that (] – o(]))lnn is a threshold below which set, cover cannot be approximated efficiently, unless NP has slightly superpolynornial time algorithms. This closes tlw gap (up to low order… Expand

Set cover algorithms for very large datasets

- Computer Science
- CIKM
- 2010

In order to scale Set Cover to large datasets, this work provides a new algorithm which finds a solution that is provably close to that of greedy, but which is much more efficient to implement using modern disk technology. Expand

The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover

- Computer Science
- Theory Comput.
- 2015

It is shown that under the projection games conjecture, it is NP-hard to approximate Set-Cover on instances of size N to within (1 − α) lnN for arbitrarily small α > 0. Expand

A tight analysis of the greedy algorithm for set cover

- Mathematics, Computer Science
- STOC '96
- 1996

The first substantial improvement of the 20 year old classical harmonic upper bound, H(m), of Johnson, Lovssz, and ChvAt al is provided, and the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on the integralit~ gap. Expand

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

- Computer Science, Mathematics
- 2010 IEEE 51st Annual Symposium on Foundations of Computer Science
- 2010

The first passive memory checkers that verify the interaction transcripts of priority queues, stacks, and double-ended queues are presented, and tight upper and lower bounds are obtained for these problems, thereby addressing an important sub-class of the memory checking framework of Blum et al. Expand

A Tight Analysis of the Greedy Algorithm for Set Cover

- Mathematics, Computer Science
- J. Algorithms
- 1997

The first substantial improvement of the 20-year-old classical harmonic upper bound,H(m), of Johnson, Lovasz, and Chvatal, is provided and the approximation guarantee for the greedy algorithm is better than the guarantee recently established by Srinivasan for the randomized rounding technique, thus improving the bounds on theintegrality gap. Expand