Improved Distributed Approximate Matching

DOI10.1145/2786753zbMATH Open1426.68292OpenAlexW2275325805MaRDI QIDQ3177747FDOQ3177747

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

(36)

• Trading bit, message, and time complexity of distributed algorithms
• Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Best of two local models: centralized local and distributed local algorithms
• An improved constant-time approximation algorithm for maximum~matchings
• Distributed approximation of cellular coverage
• Improved deterministic distributed matching via rounding
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Distributed graph algorithms and their complexity: an introduction
• Algorithms – ESA 2004
• Distributed Weighted Matching
• Round compression for parallel matching algorithms
• (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 backup placement in networks
• Efficient Distributed Weighted Matchings on Trees
• Improved bounds for distributed load balancing
• Communication complexity of approximate maximum matching in the message-passing model
• An estimator for matching size in low arboricity graphs with two applications
• 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 algorithm for approximating the maximum matching
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Optimizing social welfare for network bargaining games in the face of instability, greed and idealism
• Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
• Distributed approximate maximum matching in the CONGEST model
• Distributed maximum matching verification in CONGEST
• The sparsest additive spanner via multiple weighted BFS trees
• Distributed approximate matching
• Distributed approximation of maximum independent set and maximum matching
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Distributed approximate matching
• Fast Distributed Approximation for Max-Cut
• Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC

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)