Towards improving Christofides algorithm for half-integer TSP

DOI10.4230/LIPICS.ESA.2019.56MaRDI QIDQ5075801FDOQ5075801

Authors Arash Haddadan, Alantha Newman 

Publication date 11 May 2022

zbMATH Keywords

traveling salesman problemintegrality gapgluing subtourssubtour elimination relaxation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
• A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
• An improved approximation algorithm for TSP in the half integral case
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

Cites work

• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• scientific article; zbMATH DE number 3526435 (Why is no real title available?)
• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Heuristic analysis, linear programming and branch and bound
• Integer Programming: Methods, Uses, Computations
• Matching, Euler tours and the Chinese postman
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Removing and adding edges for the traveling salesman problem
• Shorter tours and longer detours: uniform covers and a bit beyond
• 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
• Solution of a Large-Scale Traveling-Salesman Problem
• The saleman's improved tours for fundamental classes
• The traveling salesman problem in graphs with 3-edge cutsets
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph

Cited in

(4)

• Matroid-based TSP rounding for half-integral solutions
• A deterministic better-than-3/2 approximation algorithm for metric TSP
• Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
• Matroid-based TSP rounding for half-integral solutions

This page was built for publication: Towards improving Christofides algorithm for half-integer TSP

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