2017/03/21 by Zeev Nutov, Nutov, Zeev · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1703.07247
openalex publication_date 2017/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Tree Augmentation problem we are given a tree T=(V,F) and a set E ⊆ V × V of edges with positive integer costs \ce:e ∈ E\. The goal is to augment T by a minimum cost edge set J ⊆ E such that T ∪ J is 2-edge-connected. We obtain the following results. Recently, Adjiashvili [SODA 17] introduced a novel LP for the problem and used it to break the 2-approximation barrier for instances when the maximum cost M of an edge in E is bounded by a constant; his algorithm computes a 1.96418+ε approximate solution in time n^(M/ε2)O(1). Using a simpler LP, we achieve ratio (12)/(7)+ε in time 2O(M/ε2) poly(n).This gives ratio better than 2 for logarithmic costs, and not only for constant costs. One of the oldest open questions for the problem is whether for unit costs (when M=1) the standard LP-relaxation, so called Cut-LP, has integrality gap less than 2. We resolve this open question by proving that for unit costs the integrality gap of the Cut-LP is at most 28/15=2-2/15. In addition, we will prove that another natural LP-relaxation, that is much simpler than the ones in previous work, has integrality gap at most 7/4.