Approximation Algorithms for Hard Augmentation Problems

Explore the fundamental class of Network Design Problems known as Augmentation Problems in this lecture by Rico Zenklusen. Delve into the concept of increasing graph edge-connectivity by adding edges from a given set of options, starting with the elementary example of the Minimum Spanning Tree Problem. Examine the more complex task of increasing edge-connectivity from an arbitrary value k to k + 1, focusing on well-known and recently studied augmentation problems such as Tree Augmentation and Connectivity Augmentation. Discover recent approaches and advances in the field, combining classical Combinatorial Optimization techniques with innovative ideas. Gain insights into approximation algorithms for these challenging problems over the course of this 1-hour and 12-minute lecture from the Hausdorff Center for Mathematics.

Rico Zenklusen: Approximation algorithms for hard augmentation problems, lecture I