A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case

DOI10.1137/20M1372822WikidataQ114074145 ScholiaQ114074145MaRDI QIDQ5096584

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

Publication date: 18 August 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithms2-edge connectivitysubtour linear program for traveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
• 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
• Survivable networks, linear programming relaxations and the parsimonious property
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Geometric algorithms and combinatorial optimization
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• Finding 2-Factors Closer to TSP Tours in Cubic Graphs
• Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
• Heuristic analysis, linear programming and branch and bound
• Edge-Connectivity Augmentation with Partition Constraints
• Sparsification—a technique for speeding up dynamic graph algorithms
• Randomized metarounding
• An improved approximation algorithm for TSP in the half integral case
• 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
• Fully-dynamic min-cut
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• A (slightly) improved approximation algorithm for metric TSP

This page was built for publication: A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case