3 November – Vera Traub: Approximation Algorithms for Network Design Problems
The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. For example, we might require that the network stays connected even if a small number of connections fails. Many network design problems are NP-hard and thus approximation algorithms have been studied. A classical algorithm by Jain from 1998 provides a 2-approximation for a wide class of such problems and, despite intensive research in the area, still nothing better is known even for many basic special cases.
Recently, however, significant progress has been made. In a joint work with Rico Zenklusen, Traub found the first better-than-2 approximations for the weighted connectivity augmentation problem, which asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set.
This talk will give an introduction to approximation algorithms for network design. Traub will first review the iterative rounding technique from Jain’s classical algorithm and then discuss some of the techniques underlying recent progress in the area.
Vera Traub is a professor at the Research Institute for Discrete Mathematics at the University of Bonn, working mostly in the areas of combinatorial optimization and approximation algorithms. She obtained her PhD in 2020 from the University of Bonn and afterwards spent two years as a postdoctoral researcher at ETH Zurich. In 2023, she received a Maryam Mirzakhani New Frontiers Prize and a Heinz Maier-Leibnitz Prize.
