A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation

Connectivity augmentation problems are among the most elementary questions in Network Design. Many of these problems admit natural 2-approximation algorithms, often through various classic techniques, whereas it remains open whether approximation factors below 2 can be achieved. One of the most basic examples thereof is the Weighted Connectivity Augmentation Problem (WCAP). In WCAP, one is given an undirected graph together with a set of additional weighted candidate edges, and the task is to find a cheapest set of candidate edges whose addition to the graph increases its edge-connectivity. We present a (1.5+ε)-approximation algorithm for WCAP, showing for the first time that factors below 2 are achievable.