Campus Event Calendar

Event Entry

What and Who

Better-Than-2 Approximations for Weighted Tree Augmentation and Forest Augmentation

Vera Traub
University of Bonn
AG1 Mittagsseminar (own work)

Vera Traub is a junior professor at the Research Institute for Discrete Mathematics at the University of Bonn, working in the area of combinatorial optimization and approximation algorithms. Previously, she has been a postdoc at ETH Zurich in the group of Rico Zenklusen. She obtained her PhD in 2020 from the University of Bonn, under the supervision of Jens Vygen. Her PhD thesis on approximation algorithms for traveling salesman problems has received several prizes, including the EATCS Distinguished Dissertation Award. Recently, she also received a Maryam Mirzakhani New Frontiers Prize for her work on approximation algorithms for the TSP and network design.
AG 1  
AG Audience

Date, Time and Location

Tuesday, 25 October 2022
60 Minutes
Virtual talk
Virtual talk


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. In the first part of this talk we present the first algorithm that improves on the longstanding approximation ratio of 2 for WTAP.

In the second part of the talk we show how this algorithm can be used to obtain the first better-than-2 approximation algorithm for the Forest Augmentation Problem. In this problem we want to choose a minimum number of edges, among a given set of options, that we can add to a graph G to make it 2-edge connected. In contrast to the Tree Augmentation Problem, we do not require the given graph G to be connected.

This talk is based on joint works with Fabrizio Grandoni, Afrouz Jabal Ameli, and Rico Zenklusen.


Roohani Sharma
+49 681 9325 1116

Virtual Meeting Details

988 5655 4581
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk but do not have the password, contact Roohani Sharma at

Roohani Sharma, 10/20/2022 14:24
Roohani Sharma, 10/11/2022 17:39 -- Created document.