Set Cover in the One-pass Edge-arrival Streaming Model

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

We study the Set Cover problem in the one-pass edge-arrival streaming model. In this model, the input stream consists of a sequence of tuples (S, u), indicating that element u is contained in set S. This setting captures the streaming Dominating Set problem and is more general and harder to solve than the Set Cover set-arrival setting, where entire sets with all their elements arrive in the stream one-by-one. We prove the following results (n is the size of the universe, m is the number of sets):

A work by [Khanna, Konrad, ITCS'22] on streaming Dominating Set implies a one-pass Õ(√n)-approximation algorithm with space Õ (m) for edge-arrival Set Cover in adversarially ordered streams. We show that this space bound is best possible up to poly-log factors in that every α-approximation algorithm, for α = Ω(√n ), requires space Ω(mn^2/α^4 ) in adversarially ordered streams, even if the algorithm is only required to output an α-approximation of the size of an optimal cover.

As our main result, we give a one-pass Õ (√n )-approximation algorithm with space Õ (m/√n) for edge-arrival Set Cover in random order streams. This result together with the lower bound mentioned above establishes a strong separation between the adversarial and random order settings.

Finally, in adversarial order streams, we show that non-trivial algorithms with space o(m) can be achieved at the expense of increased approximation factors Ω(√n ), which is in contrast to the set-arrival setting, where space Õ (n) is enough for a Θ(√n )-approximation, and space Ω(n) is needed for an o(n/łog n)-approximation. We give an α-approximation algorithm for one-pass edge-arrival Set Cover with space Õ(mn/α^2 ), for every α = Ω(√n).
Original languageEnglish
Title of host publicationPODS 2023
Subtitle of host publicationProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
EditorsFloris Geerts, Hung Q. Ngo, Stavros Sintos
PublisherACM SIGGRAPH
Pages127-139
Number of pages13
ISBN (Electronic)979-840070127-6
DOIs
Publication statusPublished - 18 Jun 2023

Publication series

NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
ISSN (Print)1055-6338

Bibliographical note

Funding Information:
Sanjeev Khanna is supported in part by NSF awards CCF-1934876 and CCF-2008305. Christian Konrad is supported by EPSRC New Investigator Award EP/V010611/1. Cezar-Mihail Alexandru is supported by EPSRC DTP studentship EP/T517872/1.

Publisher Copyright:
© 2023 Owner/Author.

Fingerprint

Dive into the research topics of 'Set Cover in the One-pass Edge-arrival Streaming Model'. Together they form a unique fingerprint.

Cite this