An Improved Approximation Algorithm for the Matching Augmentation Problem
From MaRDI portal
Publication:5883280
Recommendations
- A simple LP-based approximation algorithm for the matching augmentation problem
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Improved approximation algorithms for stochastic matching
- A simple augmentation method for matchings with applications to streaming algorithms
- Matching Based Augmentations for Approximating Connectivity Problems
- An improved constant-time approximation algorithm for maximum~matchings
- Improved constant-time approximation algorithms for maximum matchings and other optimization problems
- An Improved Parameterized Algorithm for a Generalized Matching Problem
- An improved approximation lower bound for finding almost stable maximum matchings
- Improved linear time approximation algorithms for weighted matchings
Cites work
- scientific article; zbMATH DE number 5776838 (Why is no real title available?)
- scientific article; zbMATH DE number 6850362 (Why is no real title available?)
- 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 General Approximation Technique for Constrained Forest Problems
- 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 simple LP-based approximation algorithm for the matching augmentation problem
- 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. II
- Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
- Approximation algorithms for combinatorial optimization. 3rd international workshop, APPROX 2000, Saarbrücken, Germany, September 5--8, 2000. Proceedings
- 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
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Improved approximation for tree augmentation: saving by rewiring
- Iterative methods in combinatorial optimization.
- On the integrality ratio for tree augmentation
- On the tree augmentation 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
Cited in
(6)- Augmenting approach for some maximum set problems
- On improving matchings in trees, via bounded-length augmentations
- An improvement on Łuczak's connected matchings method
- An improved approximation algorithm for the matching augmentation problem
- scientific article; zbMATH DE number 5630441 (Why is no real title available?)
- A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation
This page was built for publication: An Improved 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 Q5883280)
