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

Augmentation Problems are a fundamental class of Network Design Problems. In short, the goal is to find a cheapest way to increase the (edge-)connectivity of a graph by adding edges from a given set of options. The Minimum Spanning Tree Problem is one of its most elementary examples, which can be interpreted as determining a cheapest way to increase the edge-connectivity of a graph from 0 to 1. It is a simple special case of the much harder task of increasing the edge- connectivity from some arbitrary value k to k + 1. This leads to some well-known and heavily studied augmentation problems that enjoyed a surge of interest recently, including (unweighted and weighted) Tree Augmentation and, more generally, Connectivity Augmentation. We will discuss some recent approaches and advances in the field, which combine classical results and techniques in Combinatorial Optimization with a variety of new ideas.