Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
Sylvia C. Boyd, Philippe Legault · SIAM Journal on Discrete Mathematics · 2017
Given a complete graph $K_{n}=(V, E)$ with nonnegative edge costs $c\in {\mathbb R}^{E}$, the problem 2EC is that of finding a 2-edge connected spanning multisubgraph of $K_{n}$ of minimum cost. The integrality gap $\alpha\text{2{\it EC}}$ of the linear programming relaxation $\text{2{\it EC}}^{\text{LP}}$ for 2EC has been conjectured to be $\frac{6}{5}$, although currently we only know that $\frac{6}{5}\leq\alpha\text{2{\it EC}}\leq\frac{3}{2}$. In this paper, we explore the idea of using the structure of solutions for $\text{2{\it EC}}^{\text{LP}}$ and the concept of convex combination to obtain improved bounds for $\alpha\text{2{\it EC}}$. We focus our efforts on a family $J$ of half-integer solutions that appear to give the largest integrality gap for $\text{2{\it EC}}^{\text{LP}}$. We successfully show that the conjecture $\alpha\text{2{\it EC}} = \frac{6}{5}$ is true for any cost functions optimized by some $x^{*}\in J$.