Bicriteria Approximation for k-Edge-Connectivity

In the k-Edge Connected Spanning Subgraph (k-ECSS) problem we are given a (multi-)graph G = (V, E) with edge costs and an integer k, and seek a min-cost k-edge-connected spanning subgraph of G. The problem admits a 2-approximation algorithm and no better approximation ratio is known. Recently, Hershkowitz, Klein, and Zenklusen [STOC 24] gave a bicriteria (1, k − 10)-approximation algorithm that computes a (k − 10)-edge-connected spanning subgraph of cost at most the optimal value of a standard Cut-LP for k-ECSS. We improve the bicriteria approximation to (1, k − 4) and also give another non-trivial bicriteria approximation (3/2, k − 2). The k-Edge-Connected Spanning Multi-subgraph (k-ECSM) problem is almost the same as k-ECSS, except that any edge can be selected multiple times at the same cost. A (1, k − p) bicriteria approximation for k-ECSS w.r.t. Cut-LP implies approximation ratio 1 + p/k for k-ECSM, hence our result also improves the approximation ratio for k-ECSM.