Dutch Seminar on Optimization (online series) with Vera Traub (ETH Zürich)
The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events.
- https://www.cwi.nl/research/groups/networks-and-optimization/events/dutch-seminar-on-optimization-online-series-with-vera-traub-eth-zurich
- Dutch Seminar on Optimization (online series) with Vera Traub (ETH Zürich)
- 2022-06-30T15:00:00+02:00
- 2022-06-30T16:00:00+02:00
- The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events.
- What English Networks & Optimization
- When 30-06-2022 from 15:00 to 16:00 (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Web Visit external website
-
Add event to calendar
iCal
Speaker: Vera Traub (ETH Zürich)
Title:
Better-Than-2 Approximations for Weighted Tree Augmentation and Forest Augmentation
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
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.