Approximation algorithms for minimum-cost k-vertex connected subgraphs
Joseph Cheriyan, Santosh Vempala, Adrian R. Vetta · 2002
We present two new algorithms for the problem of nding a minimum-cost k-vertex connected spanning subgraph. The rst algorithm works on undirected graphs with at least 6k vertices and achieves an approximation of 6 times the kth harmonic number (which is O(log k)), The second algorithm works on any graph (directed or undirected) and gives an O( n=)-approximation algorithm for any > 0 and k (1 )n. These algorithms improve on the previous best approximation factor (more than k=2). The latter algorithm also extends to other problems in network design with vertex connectivity requirements. Our main tools are setpair relaxations, a theorem of Mader's (in the undirected case) and iterative rounding (general case).