Ghost Value Augmentation for k-Edge-Connectivity

We give a poly-time algorithm for the k -edge-connected spanning subgraph ( k -ECSS) problem that returns a solution of cost no greater than the cheapest ( k +10)-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems. Our guarantees improve upon the best-known approximation factor of 2 for k -ECSS whenever the optimal value of ( k +10)-ECSS is close to that of k -ECSS. This is a property that holds for the closely related problem k -edge-connected spanning multi-subgraph ( k -ECSM), which is identical to k -ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a 1+ O (1/ k )-approximation algorithm for k -ECSM, which resolves a conjecture of Pritchard and improves upon a recent 1+ O (1/√ k )-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for k -ECSM, showing that our approximation ratio is tight up to the constant factor in O (1/ k ), unless P=NP.

Authors

• D. Ellis Hershkowitz
• Nathan Klein
• Rico Zenklusen

Keywords

• Approximation Algorithms
• Edge Connectivity
• Iterative Rounding
• Network Design