Document Open Access Logo

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

Authors Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur , Zoltán Szigeti, Lu Wang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.61.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Sylvia Boyd
  • School of Electrical Engineering and Computer Science, University of Ottawa, Canada
Joseph Cheriyan
  • Department of Combinatorics and Optimization, University of Waterloo, Canada
Robert Cummings
  • Department of Combinatorics and Optimization, University of Waterloo, Canada
Logan Grout
  • Department of Combinatorics and Optimization, University of Waterloo, Canada
Sharat Ibrahimpur
  • Department of Combinatorics and Optimization, University of Waterloo, Canada
Zoltán Szigeti
  • University Grenoble Alpes, CNRS, G-SCOP, France
Lu Wang
  • Department of Combinatorics and Optimization, University of Waterloo, Canada

Funding

  • Cheriyan, Joseph: Supported by NSERC RGPIN-2019-04197.
  • Ibrahimpur, Sharat: Supported in part by NSERC grant 327620-09.

Acknowledgements

{SB}, {JC}, and {SI} thank BIRS, Canada for organizing the workshop on The Traveling Salesman Problem (2018), where some of the results in our references were presented.

Cite AsGet BibTex

Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, and Lu Wang. A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.61

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Routing and network design problems
Keywords
  • 2-Edge Connectivity
  • Approximation Algorithms
  • Subtour LP for TSP

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anthony Alexander, Sylvia Boyd, and Paul Elliott-Magwood. On the integrality gap of the 2-edge connected subgraph problem. Technical Report TR-2006-04, SITE, University of Ottawa, Ottawa, Canada, 2006. URL: http://www.site.uottawa.ca/~sylvia/publications/AlexanderBoydElliottmagwood2EC.pdf.
  2. Jørgen Bang-Jensen, Harold N. Gabow, Tibor Jordán, and Zoltán Szigeti. Edge-Connectivity Augmentation with Partition Constraints. SIAM Journal on Discrete Mathematics, 12(2):160-207, 1999. URL: https://doi.org/10.1137/S0895480197324700.
  3. Sylvia Boyd, Yao Fu, and Yu Sun. A 5/4-approximation for subcubic 2EC using circulations and obliged edges. Discrete Applied Mathematics, 209:48-58, 2016. URL: https://doi.org/10.1016/j.dam.2015.10.014.
  4. Sylvia Boyd, Satoru Iwata, and Kenjiro Takazawa. Finding 2-Factors Closer to TSP tours in Cubic Graphs. SIAM Journal on Discrete Mathematics, 27(2):918-939, 2013. URL: https://doi.org/10.1137/110843514.
  5. Sylvia Boyd and Philippe Legault. Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph. SIAM Journal on Discrete Mathematics, 31(1):632-644, 2017. URL: https://doi.org/10.1137/16M1057486.
  6. Robert Carr and R. Ravi. A new bound for the 2-edge connected subgraph problem. In Robert E. Bixby, E. Andrew Boyd, and Roger Z. Ríos-Mercado, editors, Integer Programming and Combinatorial Optimization, 6th International IPCO Conference, volume 1412 of Lecture Notes in Computer Science, pages 112-125. Springer, Berlin, 1998. URL: https://doi.org/10.1007/3-540-69346-7_9.
  7. András Frank. Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and its Applications, Volume 38. Oxford University Press, 2011. Google Scholar
  8. Michel X Goemans and Dimitris J Bertsimas. Survivable networks, linear programming relaxations and the parsimonious property. Mathematical Programming, 60:145-166, 1993. URL: https://doi.org/10.1007/BF01580607.
  9. Arash Haddadan. New Bounds on Integrality Gaps by Constructing Convex Combinations. PhD Thesis. Carnegie Mellon University, 2020. URL: https://www.cmu.edu/tepper/programs/phd/program/assets/dissertations/2020-joint-programs-algorithms-combinatorics-and-optimization-haddadan-dissertation.pdf.
  10. Arash Haddadan and Alantha Newman. Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes. CoRR, abs/1811.09906, 2018. URL: http://arxiv.org/abs/1811.09906.
  11. Arash Haddadan, Alantha Newman, and R. Ravi. Shorter tours and longer detours: uniform covers and a bit beyond. Mathematical Programming, 2019. URL: https://doi.org/10.1007/s10107-019-01426-8.
  12. Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. An improved approximation algorithm for TSP in the half integral case. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 28-39. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384273.
  13. Frans Schalekamp, David P. Williamson, and Anke van Zuylen. 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture. Mathematics of Operations Research, 39(2):403-417, 2014. URL: https://doi.org/10.1287/moor.2013.0608.
  14. András Sebő and Jens Vygen. Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597-629, 2014. URL: https://doi.org/10.1007/s00493-014-2960-3.
  15. David B. Shmoys and David P. Williamson. Analyzing the Held-Karp TSP bound: a monotonicity property with application. Information Processing Letters, 35(6):281-285, 1990. URL: https://doi.org/10.1016/0020-0190(90)90028-V.
  16. Laurence A. Wolsey. Heuristic analysis, linear programming and branch and bound. Mathematical Programming Study 13, pages 121-134, 1980. URL: https://doi.org/10.1007/BFb0120913.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact