BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Vera Traub (ETH Zürich)
DTSTART:20220504T170000Z
DTEND:20220504T180000Z
DTSTAMP:20260423T021016Z
UID:TCSPlus/41
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/41/"
 >Recent Developments in Graph Augmentation Problems</a>\nby Vera Traub (ET
 H Zürich) as part of TCS+\n\n\nAbstract\nAugmentation problems are a fund
 amental class of network design problems. They ask about the cheapest way 
 to increase the (edge-)connectivity of a graph by adding edges among a giv
 en set of options. One of the most elementary and intensely studied augmen
 tation problems is the (Weighted) Tree Augmentation Problem. Here\, a span
 ning tree has to be augmented into a 2-edge-connected graph.\n\nClassic te
 chniques for network design yield 2-approximation algorithms for a wide cl
 ass of augmentation problems. For the Unweighted Tree Augmentation Problem
 \, better-than-2 approximations are known for more than 20 years. However\
 , only recently the first better-than-2 approximations have been found for
  the more general Unweighted Connectivity Augmentation Problem and Weighte
 d Tree Augmentation Problem. In this talk we will discuss these recent adv
 ances.\n
LOCATION:https://researchseminars.org/talk/TCSPlus/41/
END:VEVENT
END:VCALENDAR