Approaching 3/2 for the s-t-path TSP

The s-t-path TSP is a variant of the traveling salesman problem in which the endpoints of the tour are given and distinct. The integrality ratio of the natural linear programming relaxation is believed to be 3/2, but all approximation algorithms known so far have worse performance ratio. We show that there is a polynomial-time algorithm with approximation guarantee 3/2+ε, for any fixed ε>0.

It is well known that Wolsey's analysis of Christofides' algorithm also works for the s-t-path TSP except for the narrow cuts (in which the LP solution has value less than two). A fixed optimum tour has either a single edge in a narrow cut (then call the edge and the cut lonely) or at least three (then call the cut busy). Our algorithm ``guesses'' (by dynamic programming) lonely cuts and edges. Then we partition the instance into smaller instances and strengthen the LP, requiring value at least three for busy cuts. By setting up a k-stage recursive dynamic program, we can compute a spanning tree (V,S) and an LP solution y such that (½+O(2^-k))y is in the T-join polyhedron, where T is the set of vertices whose degree in S has the wrong parity.

This is joint work with Vera Traub.