A (1.5+ε)-Approximation Algorithm for Weighted Connectivity Augmentation
Vera Traub, Rico Zenklusen
Abstract
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.
Topics & Concepts
Approximation algorithmComputer scienceSet (abstract data type)GraphUndirected graphTask (project management)AlgorithmTheoretical computer scienceMathematicsManagementEconomicsProgramming languageComplexity and Algorithms in GraphsAdvanced Graph Theory ResearchInterconnection Networks and Systems