Publications Details
A new bound for the 2-edge connected subgraph problem
Given a complete undirected graph with non-negative costs on the edges, the 2-Edge Connected Subgraph Problem consists in finding the minimum cost spanning 2-edge connected subgraph (where multiedges are allowed in the solution). A lower bound for the minimum cost 2-edge connected subgraph is obtained by solving the linear programming relaxation for this problem, which coincides with the subtour relaxation of the traveling salesman problem when the costs satisfy the triangle inequality. The simplest fractional solutions to the subtour relaxation are the (Formula presented)-integral solutions in which every edge variable has a value which is a multiple of (Formula presented). We show that the minimum cost of a 2-edge connected subgraph is at most four-thirds the cost of the minimum cost (Formula presented)-integral solution of the subtour relaxation. This supports the long-standing (Formula presented) Conjecture for the TSP, which states that there is a Hamilton cycle which is within (Formula presented) times the cost of the optimal subtour relaxation solution when the costs satisfy the triangle inequality.