[Facets-of-complexity] Invitation to Monday Lecture - Jan 10 2022, 2:15 p.m., online via zoom

[Günter Rote <rote@inf.fu-berlin.de>]

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

Time: Monday, Jan 10, 2022 - 14:15 h

Lecture: Vera Traub (ETH Zürich):

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 + ε) < 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.

=====
There will be no colloquium on this Monday.