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 algorithmslocal computation algorithmsmaximum matchingsublinear algorithms

Mathematics Subject Classification ID

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

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

(18)

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

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)