Tutte Colloquium - Vera Traub

Title: Approximating Weighted Connectivity Augmentation below Factor 2

Abstract:  The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no better-than-2 approximation algorithm has been known, whereas 2-approximations can be easily obtained through a variety of well-known techniques.

In this talk, I will discuss an approach showing that approximation factors below 2 are achievable for WCAP, ultimately leading to a (1.5 + ε)-approximation algorithm. Our approach is based on a highly structured directed simplification of WCAP with planar optimal solutions. We show how one can successively improve solutions of this directed simplification by moving to mixed-solutions, consisting of both directed and undirected edges. These insights can be leveraged in local search and relative greedy strategies, inspired by recent advances on the Weighted Tree Augmentation Problem, to obtain a (1.5 + ε)-approximation algorithm for WCAP.

This is joint work with Rico Zenklusen.