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

DOI10.1007/978-3-031-06901-7_5zbMath1497.90164arXiv2202.07283OpenAlexW4285214451MaRDI QIDQ2164677

Marina Drygala, Ola Svensson, Étienne Bamas

Publication date: 16 August 2022

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

zbMATH Keywords

integrality gapcheap 2-edge connected subgraphmatching augmentation problem

Mathematics Subject Classification ID

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

Related Items (2)

An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation

Cites Work

• Unnamed Item
• A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
• 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
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On the integrality ratio for tree augmentation
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• LP-relaxations for tree augmentation
• Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP
• Approximating (unweighted) tree augmentation via lift-and-project. II
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
• On the tree augmentation problem
• The Design of Approximation Algorithms
• Iterative Methods in Combinatorial Optimization
• Removing and Adding Edges for the Traveling Salesman Problem
• The traveling salesman problem on a graph and some related integer polyhedra
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation Algorithms for Graph Augmentation
• Biconnectivity approximations and graph carvings
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• 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
• 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
• Improved approximation for tree augmentation: saving by rewiring
• Bridging the gap between tree and connectivity augmentation: unified and stronger approaches

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