Seminars

View all Seminars  |  Download ICal for this event

Better-Than-2 Approximations for Weighted Tree Augmentation

Series: Theory Seminar

Speaker: Dr. Vera Traub Post doctoral Researcher ETH Zurich (Switzerland)

Date/Time: Sep 10 16:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

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 this 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)+ϵ)<1.7. Second, we present a local search algorithm that achieves an approximation ratio of 1.5+ϵ (for any constant ϵ>0).
This is joint work with Rico Zenklusen.
Microsoft Teams Link:
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/

Speaker Bio:

Host Faculty: Dr. Arindam Khan