Ghost Value Augmentation for $k$-Edge-Connectivity

D Ellis Hershkowitz, Nathan Klein, Rico Zenklusen

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…