On the Tree Augmentation Problem

In the Tree Augmentation problem we are given a tree $T=(V,F)$ and a set $E \subseteq V \times V$ofedgeswithpositiveintegercosts${c_e:e \in E}$. The goal is to augment $T$ by a minimum cost edge set $J\subseteq E$ such that $T\cup 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\mathrm{/}{ϵ}^2)}^{O(1)}}$. Using a simpler LP, we achieve ratio $\frac{12}{7}+ϵ$ in time $2^{O(M\mathrm{/}{ϵ}^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\mathrm{/}15=2-2\mathrm{/}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\mathrm{/}4$.