Center for Global Studies

View Full Calendar

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

Event Type
Seminar/Symposium
Sponsor
The Department of Computer Science, University of Illinois
Location
Siebel Center 3401
Date
Sep 19, 2022   10:00 am  
Speaker
Mik Zlatin PhD student at CMU
Contact
Abigail Barrett
E-Mail
abigailb@illinois.edu
Phone
217-244-0337
Views
72
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: 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.

link for robots only