## Abstract

We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an α-approximate set cover (for any α = o(n/ log n)) using a single-pass streaming algorithm, we show that Θ (mn/α) space is both sufficient and necessary (up to an O(log n) factor); here m denotes the number of sets and n denotes the size of the universe. This provides a strong negative answer to the open question posed by Har-Peled et al. [Towards tight bounds for the streaming set cover problem, in Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS '16), pp. 371-383] regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sublinear 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 α savings in the space is achievable in this case and is the best possible. In other words, we show that Θ (mn/α 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 α. 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.

Original language | English (US) |
---|---|

Pages (from-to) | 341-376 |

Number of pages | 36 |

Journal | SIAM Journal on Computing |

Volume | 50 |

Issue number | 3 |

DOIs | |

State | Published - 2021 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- Communication complexity
- Covering integer programs
- Set cover
- Streaming algorithms