Abstract: In this talk, I will discuss the Steiner Tree Augmentation Problem (STAP), in which we seek to cheaply boost the connectivity of a given Steiner tree $T$ into a 2-edge-connected Steiner subgraph. Edge-weighted STAP generalizes the classic Tree Augmentation Problem, and can be approximated to within a factor of 2 using Jain’s iterative rounding algorithm. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular we achieve a ratio of $(1.5+ \varepsilon)$ using the Local Greedy approach of Traub and Zenklusen, and generalize their main decomposition theorem from links of size two to hyper-links. In the node-weighted setting, we give a $\log^2(|T|)$-approximation using a greedy algorithm leveraging the spider decomposition of optimal solutions.
This is joint work with R. Ravi and Weizhong Zhang.