BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: The Weighted Tree Augmentation Problem (WTAP) is one of the mo
st basic connectivity augmentation problems. It asks how to increase the ed
ge-connectivity of a given graph from 1 to 2 in the cheapest possible way b
y adding some additional edges from a given set. There are many standard te
chniques that lead to a 2-approximation for WTAP\, but despite much progres
s on special cases\, the factor 2 remained unbeaten for several decades.
In this talk we present two algorithms for WTAP that improve on the longst
anding approximation ratio of 2. The first algorithm is a relative greedy a
lgorithm\, which starts with a simple\, though weak\, solution and iterativ
ely replaces parts of this starting solution by stronger components. This a
lgorithm achieves an approximation ratio of (1 + ln 2 + ε) <\; 1.7. Secon
d\, we present a local search algorithm that achieves an approximation rati
o of 1.5 + ε (for any constant ε >\; 0). This is joint work with Rico
Zenklusen.
DTSTAMP:20220107T160100
DTSTART:20220110T141500
CLASS:PUBLIC
LOCATION:online via zoom
SEQUENCE:0
SUMMARY:Vera Traub (ETH Zürich): Better-Than-2 Approximations for Weighted
Tree Augmentation
UID:107919961@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20220110-L-Traub.html
END:VEVENT
END:VCALENDAR