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

Given a complete graph $K_n=(V,E)$ with non-negative edge costs $c\in {\mathbb R}^{E}$,theproblem$2EC$ is that of finding a 2-edge connected spanning multi-subgraph of $K_n$ of minimum cost. The integrality gap $\alpha \text{2EC}$ of the linear programming relaxation ${\text{2EC}}^{\text{LP}}$ for $2EC$ has been conjectured to be $\frac{6}{5}$, although currently we only know that $\frac{6}{5}\le \alpha \text{2EC}\le \frac{3}{2}$. In this paper, we explore the idea of using the structure of solutions for ${\text{2EC}}^{\text{LP}}$ and the concept of convex combination to obtain improved bounds for $\alpha \text{2EC}$. We focus our efforts on a family $J$ of half-integer solutions that appear to give the largest integrality gap for ${\text{2EC}}^{\text{LP}}$. We successfully show that the conjecture $\alpha \text{2EC}=\frac{6}{5}$ is true for any cost functions optimized by some $x^{\ast }\in J$.