Improving on the 1.5-Approximation of a Smallest 2-Edge Connected Spanning Subgraph
Joseph Cheriyan, András Sebö, Zoltán Szigeti · SIAM Journal on Discrete Mathematics · 2001
We give a $\frac{17}{12}$-approximation algorithm for the following NP-hard problem: Given a simple undirected graph, find a 2-edge connected spanning subgraph that has the minimum number of edges. The best previous approximation guarantee was $\frac{3}{2}$. If the well-known $\frac{4}{3}$ conjecture for the metric traveling salesman problem holds, then the optimal value (minimum number of edges) is at most $\frac{4}{3}$ times the optimal value of a linear programming relaxation. Thus our main result gets halfway to this target.