New and improved approximation algorithms for Steiner Tree Augmentation Problems
share
In the Steiner Tree Augmentation Problem (STAP), we are given a graph G = (V,E), a set of terminals R ⊆ V, and a Steiner tree T spanning R. The edges L := E ∖ E(T) are called links and have non-negative costs. The goal is to augment T by adding a minimum cost set of links, so that there are 2 edge-disjoint paths between each pair of vertices in R. This problem is a special case of the Survivable Network Design Problem which can be approximated to within a factor of 2 using iterative rounding <cit.>. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular we achieve a ratio of (1+ ln 2 + ε) ≈ 1.69 + ε. To do this, we use the Local Greedy approach of <cit.> for the Tree Augmentation Problem and generalize their main decomposition theorem from links (of size two) to hyper-links. We also consider the Node-Weighted Steiner Tree Augmentation Problem (NW-STAP) in which the non-terminal nodes have non-negative costs. We seek a cheapest subset S ⊆ V ∖ R so that G[R ∪ S] is 2-edge-connected. We provide a O(log^2 (|R|))-approximation algorithm for NW-STAP. To do this, we use a greedy algorithm leveraging the spider decomposition of optimal solutions.
READ FULL TEXT