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

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

zbMATH Keywords

traveling salesman problemintegrality gapgluing subtourssubtour elimination relaxation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

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

Cited In (4)

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

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)