Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
From MaRDI portal
Publication:2687058
DOI10.1007/s10107-022-01784-wOpenAlexW3033262378MaRDI QIDQ2687058
Arash Haddadan, Alantha Newman
Publication date: 1 March 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.02120
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
- 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
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
- Worst-case comparison of valid inequalities for the TSP
- Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
- Shorter tours and longer detours: uniform covers and a bit beyond
- The salesman's improved tours for fundamental classes
- On the approximability of the traveling salesman problem
- Finding 2-Factors Closer to TSP Tours in Cubic Graphs
- The Design of Approximation Algorithms
- Removing and Adding Edges for the Traveling Salesman Problem
- Integer Programming
- The traveling salesman problem in graphs with 3-edge cutsets
- Heuristic analysis, linear programming and branch and bound
- Spanning trees with many or few colors in edge-colored graphs
- Halin graphs and the travelling salesman problem
- Matching, Euler tours and the Chinese postman
- 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
- Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
- A Randomized Rounding Approach to the Traveling Salesman Problem
- A (slightly) improved approximation algorithm for metric TSP
This page was built for publication: Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours