An Improved Approximation Algorithm for the Minimum $k$-Edge Connected Multi-Subgraph Problem

Abstract

We give a randomized $1+\frac{5.06}{\sqrt{k}}$-approximation algorithm for the minimum $k$-edge connected spanning multi-subgraph problem, $k$-ECSM.