Towards Tight Bounds for the Streaming Set Cover Problem

Towards Tight Bounds for the Streaming Set Cover Problem

We consider the classic Set Cover problem in the data stream model. For n elements and m sets (m ≥ n) we give a O(1/δ)-pass algorithm with a strongly sub-linear ~O(mn[superscript δ]) space and logarithmic approximation factor. This yields a significant improvement over the earlier algorithm of Demai...

Full description

Bibliographic Details
Main Authors: Har-Peled, Sariel, Indyk, Piotr, Mahabadi, Sepideh, Vakilian, Ali
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Association for Computing Machinery 2018
Online Access:http://hdl.handle.net/1721.1/113829
https://orcid.org/0000-0002-7983-9524
https://orcid.org/0000-0001-5049-7594
https://orcid.org/0000-0001-5004-8991

Internet

http://hdl.handle.net/1721.1/113829
https://orcid.org/0000-0002-7983-9524
https://orcid.org/0000-0001-5049-7594
https://orcid.org/0000-0001-5004-8991

Similar Items