A simple LP-based approximation algorithm for the matching augmentation problem

DOI10.1007/978-3-031-06901-7_5MaRDI QIDQ2164677zbMATH OpenOpenAlexFDO

Authors Étienne Bamas, Marina Drygala, Ola Svensson

Publication date 16 August 2022

Full work available at URL https://arxiv.org/abs/2202.07283

zbMATH Keywords

cheap 2-edge connected subgraphintegrality gapmatching augmentation problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap $2$-edge connected subgraphs. This has culminated in a $frac53$-approximation algorithm. However, the algorithm and its analysis are fairly involved and do not compare against the problem's well-known LP relaxation called the cut LP. In this paper, we propose a simple algorithm that, guided by an optimal solution to the cut LP, first selects a DFS tree and then finds a solution to MAP by computing an optimum augmentation of this tree. Using properties of extreme point solutions, we show that our algorithm always returns (in polynomial time) a better than $2$-approximation when compared to the cut LP. We thereby also obtain an improved upper bound on the integrality gap of this natural relaxation.

Recommendations

• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• On the tree augmentation problem
• LP-relaxations for tree augmentation
• Matching Based Augmentations for Approximating Connectivity Problems
• scientific article; zbMATH DE number 7205039

Cites work

• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• 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 (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Approximating (unweighted) tree augmentation via lift-and-project. II
• Approximation Algorithms for Graph Augmentation
• Approximation Algorithms for Several Graph Augmentation Problems
• Beating approximation factor two for weighted tree augmentation with bounded costs
• Biconnectivity approximations and graph carvings
• Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
• 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.
• LP-relaxations for tree augmentation
• On the integrality ratio for tree augmentation
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• On the tree augmentation problem
• Removing and adding edges for the traveling salesman problem
• 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
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• The traveling salesman problem on a graph and some related integer polyhedra

Cited in

(7)

• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• Matching Based Augmentations for Approximating Connectivity Problems
• 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

This page was built for publication: A simple LP-based approximation algorithm for the matching augmentation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164677)