An Improved Approximation Algorithm for the Matching Augmentation Problem

DOI10.1137/21M1453505OpenAlexW3215578882MaRDI QIDQ5883280FDOQ5883280

Authors:

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

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

approximation algorithms network design connectivity augmentation matching augmentation problem 2-edge connected graph 2-edge covers forest augmentation problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

The design of approximation algorithms
Combinatorial optimization. Polyhedra and efficiency (3 volumes)
A General Approximation Technique for Constrained Forest Problems
Biconnectivity approximations and graph carvings
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 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
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 factor 2 approximation algorithm for the generalized Steiner network problem
Iterative methods in combinatorial optimization.
On the integrality ratio for tree augmentation
An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
A \({(1+\ln 2)}\)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius
Title not available (Why is that?)
Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
Improved approximation for tree augmentation: saving by rewiring
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
On the tree augmentation problem
Title not available (Why is that?)
Beating approximation factor two for weighted tree augmentation with bounded costs
Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
A simple LP-based approximation algorithm for the matching augmentation problem

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
Title not available (Why is that?)
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)