An Improved Approximation Algorithm for the Matching Augmentation Problem
From MaRDI portal
Publication:5883280
DOI10.1137/21M1453505OpenAlexW3215578882MaRDI QIDQ5883280
No author found.
Publication date: 30 March 2023
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.11559
network designapproximation algorithmsconnectivity augmentationmatching augmentation problem2-edge connected graph2-edge coversforest augmentation problem
Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- 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
- Approximation algorithms for combinatorial optimization. 3rd international workshop, APPROX 2000, Saarbrücken, Germany, September 5--8, 2000. Proceedings
- Approximating (unweighted) tree augmentation via lift-and-project. II
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- A simple LP-based approximation algorithm for the matching augmentation problem
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- On the tree augmentation problem
- The Design of Approximation Algorithms
- Approximating the smallest k -edge connected spanning subgraph by LP-rounding
- Iterative Methods in Combinatorial Optimization
- 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
