Approximability of the Tree Augmentation Problem

From himtp
Revision as of 09:32, 28 September 2015 by Nutov (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

(suggested by Zeev Nutov)

Problem Statement

The Tree Augmentation Problem (TAP) is: given a graph G=(V,E) with edge costs and a tree (laminar family) T on node set V, find a min-cost augmenting edge set F \subseteq E such that T+F 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 1+\ln 2 in time roughly O(n^{2^D}), where D is the diameter of T.

Open questions

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?

Please add comments here