Events

Events folder

Santanu_Dey_25-02-2021-DutchSeminarOnOptimization.pdf

Moritz_Buchem_Additive_Approximation_Schemes_Presentation_DutchOptSem.pdf

Michelle_Sweering_Dutch_Seminar_on_Optimization_25-03-2021.pdf

jpeypou_DOS_2021.pdf

Céline_Swennenhuis_27-05-2021_Bin_Packing_CWI_final.pdf

Céline_Swennenhuis_27-05-2021_Bin_Packing_CWI_final.pptx

Slides_Samuel-Fiorini_26-08-2021_DutchSeminarOnOptimization.pdf

Slides_Martin_Skutella_DutchSeminarOnOptimization_30-09-2021.pdf

Slides_Juan_Jose_Maulen_DutchSeminarOnOptimization_25-10-2021.pdf

Slides_Lucas_Slot_DutchSeminarOnOptimization_25-10-2021.pdf

slides-britta-dutch-seminar.pdf

Slides_Hadi_Abbaszadehpeivasti_DutchSeminarOnOptimization_09-12-2021.pdf

Slides_Utku_Karaca_DutchSeminarOnOptimization_09-12-2021.pdf

Dutch-optimization-seminar-UFP-PTAS.pptx

IP_Friedrich_Eisenbrand.pdf

DonatoMaragno_Slides_DutchSeminarOnOptimization.pptx

EstebanGabory_DutchSeminarOnOptimization_Slides.pdf

Krzysztof_Postek_Robust Adaptive Scheduling.pdf

Seminar: Vera Traub (ETH Zürich)

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.

Video:

[will be inserted after the talk]

Slides

[will be inserted after the talk]