A $(4+ϵ)$-approximation for $k$-connected subgraphs

We obtain approximation ratio $2(2+\frac{1}{\mathrm{\ell }})$ for the (undirected) $k$-Connected Subgraph problem, where $\mathrm{\ell }\approx \frac{1}{2}({\log }_{k}n-1)$ is the largest integer such that $2^{\mathrm{\ell }-1}{k}^{2\mathrm{\ell }+1}\le n$. For large values of $n$ this improves the $6$-approximation of Cheriyan and V'egh when $n=\mathrm{\Omega }(k^3)$, which is the case $\mathrm{\ell }=1$. For $k$ bounded by a constant we obtain ratio $4+ϵ$. For large values of $n$ our ratio matches the best known ratio $4$ for the augmentation version of the problem, as well as the best known ratios for $k=6,7$. Similar results are shown for the problem of covering an arbitrary crossing supermodular biset function.