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

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

被引用 6 次

摘要

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