2025/07/04 by Nutov, Zeev, Cohen, Reut · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2507.03786
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.