Improving Christofides' algorithm for the s-t path TSP

DOI10.1145/2818310zbMATH Open1426.68300arXiv1110.4604OpenAlexW2240814884MaRDI QIDQ3177743FDOQ3177743

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

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We present a deterministic (1+sqrt(5))/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact has been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides' algorithm variant. Our algorithm also proves an upper bound of (1+sqrt(5))/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.

Full work available at URL: https://arxiv.org/abs/1110.4604

Recommendations

• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Approaching \(\frac 23\) for the \(s\)-\(t\)-path TSP
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• On the metric \(s\)-\(t\) path traveling salesman problem

zbMATH Keywords

approximation algorithmstraveling salesman problemlinear programming relaxationsrounding algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cited In (22)

• A constant-factor approximation for directed latency in quasi-polynomial time
• Reducing Path TSP to TSP
• Approximating the multiple-depot multiple-terminal Hamiltonian path problem
• A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time
• Algorithms for Euclidean Degree Bounded Spanning Tree Problems
• A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
• A LP-based approximation algorithm for generalized traveling salesperson path problem
• Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
• Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
• Improving the robustness of EPS to solve the TSP
• Scheduling on a graph with release times
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• Better \(s-t\)-tours by Gao trees
• An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
• Layers and matroids for the traveling salesman's paths
• Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
• An approximation algorithm for the clustered path travelling salesman problem
• An approximation algorithm for the clustered path travelling salesman problem
• Improving on best-of-many-Christofides for \(T\)-tours
• Approximation algorithms with constant ratio for general cluster routing problems
• Polyhedral techniques in combinatorial optimization: matchings and tours

This page was built for publication: Improving Christofides' algorithm for the \(s\)-\(t\) path TSP

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