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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| 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 |