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.

----------------------------------

Speaker's Webpage

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