Theory Seminar

Friday, October 22, 2021 - 3:00pm to 4:00pm

Location:

In Person and Virtual ET Gates Hillman 8102 and Zoom

Speaker:

VERA TRAUB, Postdoctoral Researcher https://people.math.ethz.ch/~vtraub/

Better-Than-2 Approximations for Weighted Tree Augmentation

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.

In Person and Zoom Participation. See announcement.

Event Website:

http://theory.cs.cmu.edu/

For More Information, Contact:

Keywords:

Seminar Series