Improved Distributed Approximate Matching
From MaRDI portal
Publication:3177747
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
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
Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)
Cited In (36)
- 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
- The Sparsest Additive Spanner via Multiple Weighted BFS Trees
- Optimizing social welfare for network bargaining games in the face of instability, greed and idealism
- 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
- Distributed approximate matching
- Algorithms – ESA 2004
- Distributed Weighted Matching
- Round compression for parallel matching algorithms
- Improved deterministic distributed matching via rounding
- Distributed maximum matching verification in CONGEST
- Distributed algorithms for covering, packing and maximum weighted matching
- On the complexity of distributed stable matching with small messages
- 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)
