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.