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

DOI10.4230/lipics.approx/random.2020.61OpenAlexW3048051264MaRDI QIDQ6058192

Sharat Ibrahimpur, Joseph Cheriyan, Robert Cummings, Logan Grout, Zoltán Szigeti, Sylvia Boyd, Unnamed Author

Publication date: 31 October 2023

Full work available at URL: https://arxiv.org/abs/2008.03327

zbMATH Keywords

approximation algorithms2-edge connectivitysubtour LP for TSP

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes

This page was built for publication: A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected

 Multisubgraph Problem in the Half-Integral Case