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

2021/01/15 by Karlin, Anna R., Klein, Nathan, Gharan, Shayan Oveis +1 · 3 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2101.05921

Abstract

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

Cited by

• Improved bicriteria approximation for k-edge-connectivity
• Bicriteria approximation for k-edge-connectivity
• Almost Tight Additive Guarantees for k-Edge-Connectivity

Related

• Improved bicriteria approximation for k-edge-connectivity
• Bicriteria approximation for k-edge-connectivity
• Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
• Ghost Value Augmentation for k-Edge-Connectivity
• k-Edge-Connectivity: Approximation and LP Relaxation