Approximability of the Tree Augmentation Problem
(suggested by Zeev Nutov)
The Tree Augmentation Problem (TAP) is: given a graph with edge costs and a tree (laminar family) on node set , find a min-cost augmenting edge set such that is 2-edge connected. TAP is a particular case of the Min-Cost 2-Edge-Connected Subgraph problem, when the input graph contains a spanning tree of cost zero.
What is known?
1. The problem admits several 2-approximation algorithms.
2. The integrality gap of a standard cut-LP is in the range [1.5,2].
3. For unit/uniform costs ratio 1.5 is known, but it is not related to the cut-LP.
4. For unit/uniform costs there are several extensions of the cut-LP with integrality gap better than 2.
5. The Relative Greedy heuristic gives ratio in time roughly , where is the diameter of .
Does TAP with arbitrary costs admit ratio better than 2?
Does the cut-LP have integrality gap better than 2 in the case of unit costs?