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
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
