Improved Distributed Approximate Matching

DOI10.1145/2786753MaRDI QIDQ3177747zbMATH OpenOpenAlexFDO

Authors Zvi Lotker, Boaz Patt-Shamir, Seth Pettie

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

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

Recommendations

• Distributed approximate matching
• Distributed approximate matching
• Distributed near-optimal matching
• Distributed near-optimal matching
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Improved deterministic distributed matching via rounding
• Improved deterministic distributed matching via rounding
• Distributed algorithm for approximating the maximum matching
• Algorithms – ESA 2004

Cited in

(39)

• An improved constant-time approximation algorithm for maximum~matchings
• Fast Distributed Approximation for Max-Cut
• Communication complexity of approximate maximum matching in the message-passing model
• Distributed backup placement in networks
• Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
• Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective
• An estimator for matching size in low arboricity graphs with two applications
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Distributed approximation of cellular coverage
• Improved bounds for distributed load balancing
• Trading bit, message, and time complexity of distributed algorithms
• The sparsest additive spanner via multiple weighted BFS trees
• Best of two local models: centralized local and distributed local algorithms
• Approximating bipartite minimum vertex cover in the Congest model
• Optimizing social welfare for network bargaining games in the face of instability, greed and idealism
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Distributed algorithm for approximating the maximum matching
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Distributed approximation of maximum independent set and maximum matching
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Distributed graph algorithms and their complexity: an introduction
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Efficient Distributed Weighted Matchings on Trees
• The message complexity of distributed graph optimization
• Distributed approximate matching
• Round compression for parallel matching algorithms
• Algorithms – ESA 2004
• Distributed Weighted Matching
• Distributed algorithms for covering, packing and maximum weighted matching
• On the complexity of distributed stable matching with small messages
• Improved deterministic distributed matching via rounding
• Distributed maximum matching verification in CONGEST
• Distributed approximate maximum matching in the CONGEST model
• Improved deterministic distributed matching via rounding
• Distributed approximate matching

This page was built for publication: Improved Distributed Approximate Matching

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