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

SEPEHR ASSADI, SANJEEV KHANNA, YANG LI

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)341-376
Number of pages36
JournalSIAM Journal on Computing
Volume50
Issue number3
DOIs
StatePublished - 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

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

Fingerprint

Dive into the research topics of 'Tight bounds for single-pass streaming complexity of the set cover problem'. Together they form a unique fingerprint.

Cite this