An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang

6 citations

Abstract

We give a randomized 1+5.06/√k-approximation algorithm for the minimum k-edge connected spanning multi-subgraph problem, k-ECSM.