Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP

DOI10.1007/s00453-016-0270-4zbMath1395.90232arXiv1508.07504OpenAlexW2963428578MaRDI QIDQ1709580

Joseph Cheriyan, Zhihan Gao

Publication date: 6 April 2018

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingsemidefinite programmingnetwork designgraph connectivityapproximation algorithmsconnectivity augmentationlift-and-projectalgorithmic aspects of networks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (7)

A simple LP-based approximation algorithm for the matching augmentation problem ⋮ Node connectivity augmentation via iterative randomized rounding ⋮ Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ On small-depth tree augmentations ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Covering a laminar family by leaf to leaf links
• On the integrality ratio for tree augmentation
• Approximating (unweighted) tree augmentation via lift-and-project. II
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
• Approximation Algorithms for Several Graph Augmentation Problems
• LP-Relaxations for Tree Augmentation.
• Hardness of Approximation for Vertex-Connectivity Network Design 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

This page was built for publication: Approximating (unweighted) tree augmentation via lift-and-project. I: Stemless TAP