The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm

DOI10.1007/S10107-019-01394-ZzbMath1452.90309arXiv1810.07816OpenAlexW3105989759MaRDI QIDQ2191772

Vishnu V. Narayan, Arindam Khan, Fabrizio Grandoni, J. Dippel, Joseph Cheriyan

Publication date: 26 June 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

network designapproximation algorithmsbridgesconnectivity augmentationmatching augmentation problem2-edge connected graph2-edge coversforest augmentation problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ Flexible Graph Connectivity ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ How to Secure Matchings against Edge Failures ⋮ A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation ⋮ Flexible graph connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• New inapproximability bounds for TSP
• A factor 2 approximation algorithm for the generalized Steiner network problem
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• The Design of Approximation Algorithms
• Approximating the smallest k -edge connected spanning subgraph by LP-rounding
• Iterative Methods in Combinatorial Optimization
• Approximation Algorithms for Several Graph Augmentation Problems
• 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
• Improved approximation for tree augmentation: saving by rewiring

This page was built for publication: The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm