Improving christofides' algorithm for the s-t path TSP
From MaRDI portal
Publication:5415521
DOI10.1145/2213977.2214055zbMath1286.68173MaRDI 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
approximation algorithms; TSP (traveling salesman problem); linear programming relaxations and rounding algorithms
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
05C38: Paths and cycles
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
On the Metric $s$--$t$ Path Traveling Salesman Problem, TSP Tours in Cubic Graphs: Beyond 4/3, On the Metric $s$--$t$ Path 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, \(\frac{13}{9}\)-approximation for graphic TSP, Approximating minimum-cost connected \(T\)-joins, An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem, An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem, An LP-based approximation algorithm for the generalized traveling salesman path problem, Reassembling Trees for the Traveling Salesman, Unnamed Item, Better s-t-Tours by Gao Trees, An Improved Integrality Gap for Asymmetric TSP Paths
