Improved approximations for TSP with simple precedence constraints

In this paper, we consider the ordered TSP, a variant of the traveling salesman problem with precedence constraints, where the precedence constraints are such that a given subset of vertices has to be visited in some prescribed linear order. We give improved algorithms for the ordered TSP: For the metric case, we present a polynomial-time algorithm that guarantees an approximation ratio of 2.5−2/k2.5−2/k, where k is the number of ordered vertices. For near-metric input instances satisfying a β  -relaxed triangle inequality, we improve the ratio to kβlog2(⌊3k/2⌋+1)kβlog2(⌊3k/2⌋+1).