Theory Lunch Seminar
— 1:00pm
Speaker:
MIK ZLATIN
,
Ph.D. Student, Program in Algorithms, Combinatorics and Optimization,Tepper School of BusinessCarnegie Mellon University
https://mzlatin.github.io/
New and Improved Algorithms for Steiner Tree Augmentation Problems
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.
The Theory Lunch is sponsored in part by Smart Contract Research Forum. In Person and Zoom Participation. See announcement.
Event Website:
https://www.cs.cmu.edu/~theorylunch/