
arXiv: 1810.07816
We present a $\frac74$ 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 $\frac74$ 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 (`Factor 4/3 approximations for minimum 2-connected subgraphs,' APPROX 2000, LNCS 1913, pp.262-273).
[v2]: based on a thorough journal review, the submission has been revised to improve the exposition, though the results and proofs are the same (modulo expository improvements); there are several changes, mostly in sections 4, 5, 6; more informal discussion (of the credit scheme) has been added in sections 5.2 and 5.3; nevertheless, sections 4.4 and 5.3 need patience and effort
FOS: Computer and information sciences, connectivity augmentation, 68W25, 90C59, 90C27, 68R10, 05C85, 2-edge connected graph, network design, forest augmentation problem, Programming involving graphs or networks, Approximation methods and heuristics in mathematical programming, matching augmentation problem, Approximation algorithms, bridges, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), approximation algorithms, 2-edge covers
FOS: Computer and information sciences, connectivity augmentation, 68W25, 90C59, 90C27, 68R10, 05C85, 2-edge connected graph, network design, forest augmentation problem, Programming involving graphs or networks, Approximation methods and heuristics in mathematical programming, matching augmentation problem, Approximation algorithms, bridges, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), approximation algorithms, 2-edge covers
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
