Abstract
Given a connected undirected graph on vertices, and non-negative edge costs , the 2ECM problem is that of finding a -edge~connected spanning multisubgraph of 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 , gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution , Carr and Ravi (1998) showed that the integrality gap is at most : they show that the vector dominates a convex combination of incidence vectors of -edge connected spanning multisubgraphs of . 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 -approximation algorithm for half-integral instances. Given a half-integral solution to the LP for 2ECM, we give an -time algorithm to obtain a -edge connected spanning multisubgraph of whose cost is at most .
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.