College of Engineering Seminars & Speakers

Back to Listing

Theory Seminar: Mik Zlatin "New and Improved Algorithms for Steiner Tree Augmentation Problems"

Event Type
The Department of Computer Science, University of Illinois
Siebel Center 3401
Sep 19, 2022   10:00 am  
Mik Zlatin PhD student at CMU
Abigail Barrett
Originating Calendar
Computer Science Speakers Calendar

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:

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.

link for robots only