A 4/34/3-Approximation Algorithm for the Minimum 22-Edge Connected Multisubgraph Problem in the Half-Integral Case

preprint2020arXivOpen access

Abstract

Given a connected undirected graph Gˉ\bar{G} on nn vertices, and non-negative edge costs cc, the 2ECM problem is that of finding a 22-edge~connected spanning multisubgraph of Gˉ\bar{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ˉ\bar{G}, gives a lower bound on the optimal cost. For instances where this LP is optimized by a half-integral solution xx, Carr and Ravi (1998) showed that the integrality gap is at most 43\frac43: they show that the vector 43x\frac43 x dominates a convex combination of incidence vectors of 22-edge connected spanning multisubgraphs of Gˉ\bar{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 43\frac43-approximation algorithm for half-integral instances. Given a half-integral solution xx to the LP for 2ECM, we give an O(n2)O(n^2)-time algorithm to obtain a 22-edge connected spanning multisubgraph of Gˉ\bar{G} whose cost is at most 43cTx\frac43 c^T x.

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 reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.