Algorithms & Randomness Center (ARC)
Rico Zenklusen (ETH Zurich)
Monday, March 1, 2021
Virtual via Bluejeans - 11:00 am
Title: Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches
Abstract: The Connectivity Augmentation Problem (CAP) is one of the most basic survivable network design problems. It asks about increasing the edge-connectivity of a graph G by one unit through adding a smallest number of additional edges from a given set. If the edge-connectivity of G is odd, it reduces to a heavily studied special case known as the Tree Augmentation Problem (TAP). Despite significant recent progress on TAP, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain an approximation algorithm for CAP with guarantee better than 2 by presenting a 1.91-approximation based on techniques disjoint from recent TAP advances.
In this talk, I will present new methods that allow for leveraging insights and techniques from TAP to approach CAP. Combined with a novel analysis technique, we obtain a 1.393-approximation for CAP. This significantly improves in a unified way on the previously best approximation factor for CAP (1.91) and also TAP (1.458).
This is joint work with Federica Cecchetto and Vera Traub.
----------------------------------
Videos of recent talks are available at: http://arc.gatech.edu/node/121
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
