A Local Computation Approximation Scheme to Maximum Matching

DOI10.1007/978-3-642-40328-6_19MaRDI QIDQ2851862zbMATH OpenOpenAlexFDO

Authors Yishay Mansour, Shai Vardi

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5003

zbMATH Keywords

approximation algorithmsmaximum matchingsublinear algorithmslocal computation algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We present a polylogarithmic local computation matching algorithm which guarantees a $(1-eps)$-approximation to the maximum matching in graphs of bounded degree.

Recommendations

• Approximating maximum acyclic matchings by greedy and local search strategies
• Algorithms – ESA 2004
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Local search approaches in stable matching problems
• Locally searching for large induced matchings
• Matroid matching: the power of local search
• Matroid matching: the power of local search
• Maximum locally stable matchings
• An improvement on parallel computation of a maximal matching
• Approximating matchings in parallel

Cited in

(17)

• A local interaction dynamic for the matching problem
• Sampling and output estimation in distributed algorithms and LCAs
• Matroid matching: the power of local search
• Average Sensitivity of Graph Algorithms
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• New techniques and tighter bounds for local computation algorithms
• Best of two local models: centralized local and distributed local algorithms
• Locally computing edge orientations
• Can we locally compute sparse connected subgraphs?
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Constant-time local computation algorithms
• Local computation algorithms for spanners
• Spanning adjacency oracles in sublinear time
• Local algorithms for sparse spanning graphs
• Distributed maximum matching verification in CONGEST
• Nearly optimal local algorithms for constructing sparse spanners of clusterable graphs
• Local computation algorithms for graphs of non-constant degrees

This page was built for publication: A Local Computation Approximation Scheme to Maximum Matching

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