The matching augmentation problem: a 74-approximation algorithm
From MaRDI portal
Publication:2191772
Abstract: We present a 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 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).
Recommendations
- A simple LP-based approximation algorithm for the matching augmentation problem
- Matching Based Augmentations for Approximating Connectivity Problems
- Approximation Algorithms for Graph Augmentation
- scientific article; zbMATH DE number 1833404
- A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
Cites work
- A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A General Approximation Technique for Constrained Forest Problems
- A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
- Approximation Algorithms for Several Graph Augmentation Problems
- Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Graph theory
- scientific article; zbMATH DE number 1670548 (Why is no real title available?)
- scientific article; zbMATH DE number 6850362 (Why is no real title available?)
- Improved approximation for tree augmentation: saving by rewiring
- Iterative methods in combinatorial optimization.
- New inapproximability bounds for TSP
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
- The design of approximation algorithms
Cited in
(11)- Flexible graph connectivity
- A simple LP-based approximation algorithm for the matching augmentation problem
- Matching Based Augmentations for Approximating Connectivity Problems
- Flexible Graph Connectivity
- How to Secure Matchings against Edge Failures
- An Improved Approximation Algorithm for the Matching Augmentation Problem
- An improved approximation algorithm for the matching augmentation problem
- A (1.5+)-approximation algorithm for weighted connectivity augmentation
- A 4/3 approximation for 2-vertex-connectivity
- Better-than-2 approximations for weighted tree augmentation and applications to Steiner tree
- Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
This page was built for publication: The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2191772)
