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.