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   Info

AG Audience

English

60 Minutes

Saarbrücken

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

Zoom

988 5655 4581

passcode not visible

logged in users only

If you wish to attend the talk but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.