Given a set of cities and a function that gives the cost of traveling from one city to another, the traveling salesman problem (TSP) determines a circuit of minimal cost that 1) starts and ends in the same city and 2) passes through each city only once. A cost function that satisfies the triangle inequality is called a metric, and the corresponding TSP is called the metric TSP. A slight generalization is the metric s--t path TSP in which “the goal is to find a Hamiltonian path from s to t of minimum cost.”

An approximation algorithm for an NP-hard problem such as TSP and its variants gives, in polynomial time, a solution that lies within some predefined multiplicative factor of an optimal solution. It is shown “that an {s--t}-tour of cost at most 1.5 times the optimum can be found in polynomial time.” However, it is an open problem whether this bound can be replaced by 1.5 OPT_LP, where OPT_LP is the optimum cost for the subtour elimination linear program (LP) in which every city is entered and exited exactly once and every subset of cities is entered and exited at least once.

In this paper, the authors present a “strongly polynomial-time algorithm” with a cost less than 1.53 times the optimum of the subtour elimination LP for the metric s--t path TSP. The results, initially presented at the IEEE 57th Annual Symposium on Foundation of Computer Science (FOCS), held in 2016, will be of interest to students and researchers studying approximation algorithms.