Breaching the 2-Approximation Barrier for Connectivity Augmentation

Explore a groundbreaking lecture on the Connectivity Augmentation Problem (CAP) presented by Afrouz Jabal Ameli at the Hausdorff Center for Mathematics. Delve into the state-of-the-art research that breaches the long-standing 2-approximation barrier for CAP. Learn about the classification of links, incident links, and the innovative reduction to the Steiner Tree problem. Discover the lower bound techniques, approximation algorithms, and the novel marking scheme that led to this significant advancement. Examine the analysis of the approximation factor, grouping strategies, and recent advances in the field. Conclude with a discussion on open problems, providing insights into future research directions in graph connectivity augmentation.

Intro
Connectivity Augmentation Problem (CAP)
State of the art (Prior to our work)
Our Results
Classification of Links
Incident Links
Reduction to Steiner Tree
Reduction to the Steiner Tree Problem
Reduction from CAP to Steiner Tree
Lower Bound
Obtaining Approximation Algorithm
Steiner Tree Algorithm
How to improve?
Our Marking Scheme
Upper Bound for
Analysis of the Approximation Factor
Grouping
Recent Advances
Open Problems