We study the k-edge-connected spanning subgraph (k-ECSS) problem: given an undirected graph G with nonnegative edge costs, the objective is to find a minimum-cost k-edge-connected spanning subgraph. For even k, we present a polynomial-time algorithm that constructs a k-edge-connected subgraph whose cost is at most the optimal value of the natural LP relaxation for k-ECSS. Since k-ECSS is NP-hard for all k ≥ 2, these guarantees are nearly optimal. Moreover, our results substantially improve upon the recent work of Hershkowitz, Klein, and Zenklusen, both in approximation quality and the simplicity of the algorithm and its analysis.
