Approximating weighted tree augmentation via chvátal-gomory cuts

The weighted tree augmentation problem (WTAP) is a fundamental network design problem. We are given an undirected tree G = (V, E) with n = |V| nodes, an additional set of edges L called links and a cost vector [EQUATION]. The goal is to choose a minimum cost subset S ⊆ L such that G = (V, E ∪ S) is 2-edge-connected. In the unweighted case, that is, when we have cℓ = 1 for all ℓ ∈ L, the problem is called the tree augmentation problem (TAP).