Improved Distributed Approximate Matching

DOI10.1145/2786753zbMath1426.68292OpenAlexW2275325805MaRDI QIDQ3177747

Seth Pettie, Boaz Patt-Shamir, Zvi Lotker

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2786753

zbMATH Keywords

network algorithmsCONGEST model

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items

Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ Fast Distributed Approximation for Max-Cut ⋮ Improved deterministic distributed matching via rounding ⋮ Optimizing social welfare for network bargaining games in the face of instability, greed and idealism ⋮ Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Distributed approximation of cellular coverage ⋮ Round Compression for Parallel Matching Algorithms ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ On the complexity of distributed stable matching with small messages ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists ⋮ Distributed backup placement in networks ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC ⋮ An estimator for matching size in low arboricity graphs with two applications