An Approximation Algorithm for the Minimum-Cost k -Vertex Connected Subgraph
Joseph Cheriyan, Santosh Vempala, Adrian R. Vetta · SIAM Journal on Computing · 2003
We present an approximation algorithm for the problem of finding a minimum-cost k-vertex connected spanning subgraph, assuming that the number of vertices is at least 6k 2 . The approximation guarantee is six times the kth harmonic number (which is O(log k)), and this is also an upper bound on the integrality ratio for a standard linear programming relaxation.