LP-relaxations for tree augmentation

DOI10.1016/j.dam.2017.12.033zbMath1382.05016OpenAlexW2791470040MaRDI QIDQ1706120

Guy Kortsarz, Zeev Nutov

Publication date: 21 March 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6636/

zbMATH Keywords

approximation algorithmtree augmentationLP-relaxationLaminar family

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Flexible Graph Connectivity, A simple LP-based approximation algorithm for the matching augmentation problem, Node connectivity augmentation via iterative randomized rounding, Approximation algorithms for vertex-connectivity augmentation on the cycle, Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem, Flexible graph connectivity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Covering a laminar family by leaf to leaf links
• On the integrality ratio for tree augmentation
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Approximating (unweighted) tree augmentation via lift-and-project. II
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• A primal-dual approximation algorithm for generalized Steiner network problems
• Iterative Methods in Combinatorial Optimization
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation Algorithms for Graph Augmentation
• Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
• 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