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 |
| _version_ | 1811076080828678144 |
|---|---|
| author | Demaine, Erik D. Indyk, Piotr Mahabadi, Sepideh Vakilian, Ali |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Indyk, Piotr Mahabadi, Sepideh Vakilian, Ali |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 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 achieves a space bound of O(m ·n [superscript δ] log[superscript 2] n logm) using O(4[superscript 1/δ]) passes/rounds while achieving an approximation factor of O(4[superscript 1/δ]logn) in polynomial time (for δ = Ω(1/logn)). If we allow the algorithm/protocol to spend exponential time per pass/round, we achieve an approximation factor of O(4[superscript 1/δ]). Our approach uses randomization, which we show is necessary: no deterministic constant approximation is possible (even given exponential time) using o(m n) space. These results are some of the first on streaming algorithms and efficient two-party communication protocols for approximation algorithms. Moreover, we show that our algorithm can be applied to multi-party communication model. |
| first_indexed | 2024-09-23T10:15:52Z |
| format | Article |
| id | mit-1721.1/99997 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:15:52Z |
| publishDate | 2015 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/999972022-09-30T19:58:23Z On Streaming and Communication Complexity of the Set Cover Problem Demaine, Erik D. Indyk, Piotr Mahabadi, Sepideh Vakilian, Ali Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Indyk, Piotr Mahabadi, Sepideh Vakilian, Ali 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 achieves a space bound of O(m ·n [superscript δ] log[superscript 2] n logm) using O(4[superscript 1/δ]) passes/rounds while achieving an approximation factor of O(4[superscript 1/δ]logn) in polynomial time (for δ = Ω(1/logn)). If we allow the algorithm/protocol to spend exponential time per pass/round, we achieve an approximation factor of O(4[superscript 1/δ]). Our approach uses randomization, which we show is necessary: no deterministic constant approximation is possible (even given exponential time) using o(m n) space. These results are some of the first on streaming algorithms and efficient two-party communication protocols for approximation algorithms. Moreover, we show that our algorithm can be applied to multi-party communication model. National Science Foundation (U.S.) (Grant CCF-1161626) National Science Foundation (U.S.) (Grant CCF-1065125) United States. Defense Advanced Research Projects Agency (United States. Air Force Office of Scientific Research Grant FA9550-12-1-0423) David & Lucile Packard Foundation Simons Foundation Danish National Research Foundation. Center for Massiave Data Algorithmics (MADALGO) 2015-11-23T16:19:28Z 2015-11-23T16:19:28Z 2014 Article http://purl.org/eprint/type/ConferencePaper 978-3-662-45173-1 978-3-662-45174-8 0302-9743 1611-3349 http://hdl.handle.net/1721.1/99997 Demaine, Erik D., Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian. “On Streaming and Communication Complexity of the Set Cover Problem.” Distributed Computing (2014): 484–498. 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 en_US http://dx.doi.org/10.1007/978-3-662-45174-8_33 Distributed Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Demaine, Erik D. Indyk, Piotr Mahabadi, Sepideh Vakilian, Ali On Streaming and Communication Complexity of the Set Cover Problem |
| title | On Streaming and Communication Complexity of the Set Cover Problem |
| title_full | On Streaming and Communication Complexity of the Set Cover Problem |
| title_fullStr | On Streaming and Communication Complexity of the Set Cover Problem |
| title_full_unstemmed | On Streaming and Communication Complexity of the Set Cover Problem |
| title_short | On Streaming and Communication Complexity of the Set Cover Problem |
| title_sort | on streaming and communication complexity of the set cover problem |
| url | 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 |
| work_keys_str_mv | AT demaineerikd onstreamingandcommunicationcomplexityofthesetcoverproblem AT indykpiotr onstreamingandcommunicationcomplexityofthesetcoverproblem AT mahabadisepideh onstreamingandcommunicationcomplexityofthesetcoverproblem AT vakilianali onstreamingandcommunicationcomplexityofthesetcoverproblem |