Title: A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
| Speaker: | Sharat Ibrahimpur |
| Affiliation: | University of Waterloo |
| Zoom: | Contact Sharat Ibrahimpur |
Abstract:
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 4x/3 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 Lovasz'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 2ECM LP, we give an O(n^2)-time algorithm to obtain a 2-edge connected spanning multisubgraph of G whose cost is at most 4/3 c^T x.
This is joint work with Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Zoltan Szigeti, and Lu Wang.