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

DOI10.1137/20M1372822MaRDI QIDQ5096584zbMATH OpenWikidataFDO

Authors Sylvia Boyd, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, Lu Wang, 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

2-edge connectivityapproximation algorithmssubtour linear program for traveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected Multisubgraph Problem in the Half-Integral Case
• Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
• A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem
• scientific article; zbMATH DE number 1187146
• scientific article; zbMATH DE number 1187147

Cites work

• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• A (slightly) improved approximation algorithm for metric TSP
• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
• A factor 2 approximation algorithm for the generalized Steiner network problem
• An improved approximation algorithm for TSP in the half integral case
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Connections in combinatorial optimization
• Edge-Connectivity Augmentation with Partition Constraints
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• Finding 2-factors closer to TSP tours in cubic graphs
• Fully-dynamic MIN-cut
• Geometric algorithms and combinatorial optimization
• Heuristic analysis, linear programming and branch and bound
• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• scientific article; zbMATH DE number 2079349 (Why is no real title available?)
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Randomized metarounding
• 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
• Sparsification—a technique for speeding up dynamic graph algorithms
• Survivable networks, linear programming relaxations and the parsimonious property
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• Truthful and Near-Optimal Mechanism Design via Linear Programming

Cited in

(5)

• scientific article; zbMATH DE number 1670548 (Why is no real title available?)
• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected Multisubgraph Problem in the Half-Integral Case
• A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
• On the bidirected cut relaxation for Steiner forest

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096584)