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 + ε 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 log2(|T|)-approximation using a greedy algorithm leveraging the spider decomposition of optimal solutions.
This is joint work with R. Ravi and Weizhong Zhang.
Personal website: https://mzlatin.github.io/
Mik will be around till next Thursday so feel free to say hello and contact Rhea or Chandra Chekuri if you wish to meet with him to chat.