Computer Science Speakers Calendar

Back to Listing

Theory Seminar: Dr. Vera Traub: Better-Than-2 Approximations for Weighted Tree Augmentation

Event Type
Chandra Chekuri
wifi event
Sep 27, 2021   10:00 am  

Our next theory seminar will be on Monday, September 27, 10:00AM. The speaker for this week is Dr. Vera Traub. Vera is a postdoc at ETH in the group of Prof. Rico Zenklusen. The seminar will be online via zoom and will be projected in Siebel 3124 (masks mandatory) for those who want to attend in person.


The zoom details are:


Meeting ID: 852 3676 8481



The details of the talk are:


Title : Better-Than-2 Approximations for Weighted Tree Augmentation

Abstract: The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. There are many standard techniques that lead to a 2-approximation for WTAP, but despite much progress on special cases, the factor 2 remained unbeaten for several decades.

In this talk we present two algorithms for WTAP that improve on the longstanding approximation ratio of 2. The first algorithm is a relative greedy algorithm, which starts with a simple, though weak, solution and iteratively replaces parts of this starting solution by stronger components. This algorithm achieves an approximation ratio of (1 + ln 2 + epsilon) < 1.7. Second, we present a local search algorithm that achieves an approximation ratio of 1.5 + epsilon (for any constant epsilon > 0).

This is joint work with Rico Zenklusen.

link for robots only