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

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

Authors

• Anna R. Karlin
• Nathan Klein
• Shayan Oveis Gharan
• Xinzhi Zhang 0002

Keywords

• Approximation Algorithms
• Edge Connectivity
• Max Entropy
• Network Design
• Randomized Rounding
• Strongly Rayleigh