License:
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.61
URN: urn:nbn:de:0030-drops-126643
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12664/
Boyd, Sylvia ;
Cheriyan, Joseph ;
Cummings, Robert ;
Grout, Logan ;
Ibrahimpur, Sharat ;
Szigeti, Zoltán ;
Wang, Lu
A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
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 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.
BibTeX - Entry
@InProceedings{boyd_et_al:LIPIcs:2020:12664,
author = {Sylvia Boyd and Joseph Cheriyan and Robert Cummings and Logan Grout and Sharat Ibrahimpur and Zolt{\'a}n Szigeti and Lu Wang},
title = {{A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {61:1--61:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12664},
URN = {urn:nbn:de:0030-drops-126643},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.61},
annote = {Keywords: 2-Edge Connectivity, Approximation Algorithms, Subtour LP for TSP}
}
Keywords: |
|
2-Edge Connectivity, Approximation Algorithms, Subtour LP for TSP |
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
11.08.2020 |