Round compression for parallel matching algorithms

DOI10.1145/3188745.3188764MaRDI QIDQ5230311zbMATH OpenOpenAlexWikidataFDO

Authors Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, Piotr Sankowski, Artur Czumaj

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.03478, http://wrap.warwick.ac.uk/101747/8/WRAP-round-compression-parallel-matching-algorithms-Czumaj-2018.pdf

zbMATH Keywords

maximum matchingvertex partitioninground compression

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Abstract: For over a decade now we have been witnessing the success of {em massive parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms? A prominent example here is the {em maximum matching} problem---one of the most classic graph problems. It is well known that in the PRAM model one can compute a 2-approximate maximum matching in $O(logn)$ rounds. However, the exact complexity of this problem in the MPC framework is still far from understood. Lattanzi et al. showed that if each machine has $n^{1+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(logn)$ rounds once we enter the near-linear memory regime. It is thus entirely possible that in this regime, which captures in particular the case of sparse graph computations, the best MPC round complexity matches what one can already get in the PRAM model, without the need to take advantage of the extra local computation power. In this paper, we finally refute that perplexing possibility. That is, we break the above $O(logn)$ round complexity bound even in the case of {em slightly sublinear} memory per machine. In fact, our improvement here is {em almost exponential}: we are able to deliver a $(2+epsilon)$-approximation to maximum matching, for any fixed constant $epsilon>0$, in $O((loglogn{)}^2)$ rounds.

Recommendations

• Round compression for parallel matching algorithms
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Improved deterministic distributed matching via rounding

Cited in

(20)

• Massively parallel entity matching with linear classification in low dimensional space
• Massively parallel algorithms for approximate shortest paths
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
• Streaming graph algorithms in the massively parallel computation model
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• Efficient primal-dual graph algorithms for MapReduce
• Equivalence classes and conditional hardness in massively parallel computations
• Distributed-prover interactive proofs
• scientific article; zbMATH DE number 7651215 (Why is no real title available?)
• Exponentially faster massively parallel maximal matching
• Maliciously secure massively parallel computation for all-but-one corruptions
• Parallel derandomization for coloring
• Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Distributed algorithms for matching in hypergraphs
• scientific article; zbMATH DE number 7561507 (Why is no real title available?)
• Round compression for parallel matching algorithms
• Distributed maximum matching verification in CONGEST
• scientific article; zbMATH DE number 7525452 (Why is no real title available?)

This page was built for publication: Round compression for parallel matching algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230311)