摘要：Given a connected undirected graph G Ì. on n vertices, and non-negative edge costs c, the 2ECM problem is that of finding a 2-edge connected spanning multisubgraph of G Ì. of minimum cost. The natural linear program (LP) for 2ECM, which coincides with the subtour LP for the Traveling Salesman Problem on the metric closure of G Ì., gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution x, Carr and Ravi (1998) showed that the integrality gap is at most 4/3: they show that the vector 4/3 x dominates a convex combination of incidence vectors of 2-edge connected spanning multisubgraphs of G Ì.. We present a simpler proof of the result due to Carr and Ravi by applying an extension of Lovászâs splitting-off theorem. Our proof naturally leads to a 4/3-approximation algorithm for half-integral instances. Given a half-integral solution x to the LP for 2ECM, we give an O(n²)-time algorithm to obtain a 2-edge connected spanning multisubgraph of G Ì. whose cost is at most 4/3 c^T x.
关键词：2-Edge Connectivity; Approximation Algorithms; Subtour LP for TSP
