Round Compression for Parallel Matching Algorithms
© 2019 Society for Industrial and Applied Mathematics For over a decade now we have been witnessing the success of massive parallel computation frameworks, such as MapReduce, Hadoop, Dryad, or Spark. Compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/133650 |
| _version_ | 1826196870155730944 |
|---|---|
| author | Czumaj, Artur Ła̧cki, Jakub Ma̧dry, Aleksander Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr |
| 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 Czumaj, Artur Ła̧cki, Jakub Ma̧dry, Aleksander Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr |
| author_sort | Czumaj, Artur |
| collection | MIT |
| description | © 2019 Society for Industrial and Applied Mathematics For over a decade now we have been witnessing the success of massive parallel computation frameworks, such as MapReduce, Hadoop, Dryad, or Spark. Compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises however in this context is can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the maximum matching problem. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in O(log n) rounds. Lattanzi et al. [SPAA, ACM, New York, 2011, pp. 85-94] showed that if each machine has n1+\Omega (1) memory, this problem can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow-up work, seem though to get stuck in a fundamental way at roughly O(log n) rounds once we enter the (at most) near-linear memory regime. In this paper, we break the above O(log n) round complexity bound even in the case of slightly sublinear memory per machine. In fact, our improvement here is almost exponential: we are able to deliver a (1 + \epsilon )-approximate maximum matching for any fixed constant \epsilon > 0 in O((log log n)2) rounds. To establish our result we need to deviate from the previous work in two important ways. First, we use vertex-based graph partitioning, instead of the edge-based approaches that were utilized so far. Second, we develop a technique of round compression. |
| first_indexed | 2024-09-23T10:38:56Z |
| format | Article |
| id | mit-1721.1/133650 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:38:56Z |
| publishDate | 2021 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1336502023-12-22T20:29:53Z Round Compression for Parallel Matching Algorithms Czumaj, Artur Ła̧cki, Jakub Ma̧dry, Aleksander Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2019 Society for Industrial and Applied Mathematics For over a decade now we have been witnessing the success of massive parallel computation frameworks, such as MapReduce, Hadoop, Dryad, or Spark. Compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises however in this context is can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the maximum matching problem. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in O(log n) rounds. Lattanzi et al. [SPAA, ACM, New York, 2011, pp. 85-94] showed that if each machine has n1+\Omega (1) memory, this problem can also be solved 2-approximately in a constant number of rounds. These techniques, as well as the approaches developed in the follow-up work, seem though to get stuck in a fundamental way at roughly O(log n) rounds once we enter the (at most) near-linear memory regime. In this paper, we break the above O(log n) round complexity bound even in the case of slightly sublinear memory per machine. In fact, our improvement here is almost exponential: we are able to deliver a (1 + \epsilon )-approximate maximum matching for any fixed constant \epsilon > 0 in O((log log n)2) rounds. To establish our result we need to deviate from the previous work in two important ways. First, we use vertex-based graph partitioning, instead of the edge-based approaches that were utilized so far. Second, we develop a technique of round compression. 2021-10-27T19:54:00Z 2021-10-27T19:54:00Z 2019 2021-02-02T14:35:49Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/133650 en 10.1137/18M1197655 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Czumaj, Artur Ła̧cki, Jakub Ma̧dry, Aleksander Mitrović, Slobodan Onak, Krzysztof Sankowski, Piotr Round Compression for Parallel Matching Algorithms |
| title | Round Compression for Parallel Matching Algorithms |
| title_full | Round Compression for Parallel Matching Algorithms |
| title_fullStr | Round Compression for Parallel Matching Algorithms |
| title_full_unstemmed | Round Compression for Parallel Matching Algorithms |
| title_short | Round Compression for Parallel Matching Algorithms |
| title_sort | round compression for parallel matching algorithms |
| url | https://hdl.handle.net/1721.1/133650 |
| work_keys_str_mv | AT czumajartur roundcompressionforparallelmatchingalgorithms AT łackijakub roundcompressionforparallelmatchingalgorithms AT madryaleksander roundcompressionforparallelmatchingalgorithms AT mitrovicslobodan roundcompressionforparallelmatchingalgorithms AT onakkrzysztof roundcompressionforparallelmatchingalgorithms AT sankowskipiotr roundcompressionforparallelmatchingalgorithms |