On the Tree Augmentation Problem

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 { c_e: 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 127+ϵ 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.