An $O(k^{3}logn)$-Approximation Algorithm for Vertex-Connectivity Survivable Network Design

Julia Chuzhoy, Sanjeev Khanna

In the Survivable Network Design problem (SNDP), we are given an undirected graph $G(V,E)$ with costs on edges, along with a connectivity requirement $r(u,v)$ for each pair $u,v$ o…