Improving christofides' algorithm for the s-t path TSP

DOI10.1145/2213977.2214055zbMath1286.68173OpenAlexW2051585135MaRDI QIDQ5415521

Hyung-Chan An, David B. Shmoys, Robert D. Kleinberg

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2213977.2214055

zbMATH Keywords

approximation algorithmsTSP (traveling salesman problem)linear programming relaxations and rounding algorithms

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (13)

Better s-t-Tours by Gao Trees ⋮ An Improved Integrality Gap for Asymmetric TSP Paths ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem ⋮ 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 Metric $s$--$t$ Path Traveling Salesman Problem ⋮ \(\frac{13}{9}\)-approximation for graphic TSP ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ Reassembling Trees for the Traveling Salesman ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ Unnamed Item ⋮ Approximating minimum-cost connected \(T\)-joins

This page was built for publication: Improving christofides' algorithm for the s-t path TSP