Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Subgraph Problem

Given a complete graph Kn=(V,E) with non-negative edge costs c∈RE, the problem 2EC is that of finding a 2-edge connected spanning multi-subgraph of Kn of minimum cost. The integrality gap α2EC of the linear programming relaxation 2ECLP for 2EC has been conjectured to be , although currently we only know that . of solutions for 2ECLP and the concept of convex combination to obtain improved approximation algorithms for 2EC and bounds for α2EC. We focus our efforts on a family J of half-integer solutions that appear to give the largest integrality gap for 2ECLP. We successfully show that the conjecture is true for any cost functions optimized by some x⁎∈J. Our methods are constructive and thus also provide a -approximation algorithm for 2EC for these special cases.