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 + ε) &lt\; 1.7. Secon
 d\, we present a local search algorithm that achieves an approximation rati
 o of 1.5 + ε (for any constant ε &gt\; 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.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20220110-L-Tra
 ub.html
END:VEVENT
END:VCALENDAR