## 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).

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 language | English |
---|---|

Title of host publication | PODS 2023 |

Subtitle of host publication | Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |

Editors | Floris Geerts, Hung Q. Ngo, Stavros Sintos |

Publisher | ACM SIGGRAPH |

Pages | 127-139 |

Number of pages | 13 |

ISBN (Electronic) | 979-840070127-6 |

DOIs | |

Publication status | Published - 18 Jun 2023 |

### Publication series

Name | Proceedings 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.