On Streaming and Communication Complexity of the Set Cover Problem
We develop the first streaming algorithm and the first two-party communication protocol that uses a constant number of passes/rounds and sublinear space/communication for logarithmic approximation to the classic Set Cover problem. Specifically, for n elements and m sets, our algorithm/protocol achie...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99997 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0001-5049-7594 https://orcid.org/0000-0001-5004-8991 https://orcid.org/0000-0002-7983-9524 |