Theory Lunch Seminar September 28, 2022 12:00pm — 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/ Add event to Google Add event to iCal
