Back to Search
Start Over
The matching augmentation problem: a 74-approximation algorithm.
- Source :
-
Mathematical Programming . Jul2020, Vol. 182 Issue 1/2, p315-354. 40p. - Publication Year :
- 2020
-
Abstract
- We present a 7 4 approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. We first present a reduction of any given MAP instance to a collection of well-structured MAP instances such that the approximation guarantee is preserved. Then we present a 7 4 approximation algorithm for a well-structured MAP instance. The algorithm starts with a min-cost 2-edge cover and then applies ear-augmentation steps. We analyze the cost of the ear-augmentations using an approach similar to the one proposed by Vempala and Vetta for the (unweighted) min-size 2-ECSS problem (in: Jansen and Khuller (eds.) Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Proceedings, LNCS 1913, pp.262–273, Springer, Berlin, 2000). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 182
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 144202201
- Full Text :
- https://doi.org/10.1007/s10107-019-01394-z