Back to Search
Start Over
AN IMPROVED APPROXIMATION ALGORITHM FOR THE MATCHING AUGMENTATION PROBLEM.
- Source :
-
SIAM Journal on Discrete Mathematics . 2023, Vol. 37 Issue 1, p163-190. 28p. - Publication Year :
- 2023
-
Abstract
- We present a 5/3-approximation algorithm for the matching augmentation problem (MAP): given a multigraph 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. A 7/4-approximation algorithm for the same problem was presented recently; see Cheriyan et al. [Math. Program., 182 (2020), pp. 315--354]. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*MULTIGRAPH
*GRAPH connectivity
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 37
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 163596205
- Full Text :
- https://doi.org/10.1137/21M1453505