Improved approximations for ordered TSP on near-metric graphs^∗,∗∗

Department of Computer Science, ETH Zurich, Switzerland.
hjb@inf.ethz.ch,monika.steinova@inf.ethz.ch

Received: 6 August 2013
Accepted: 31 March 2014

Abstract

The traveling salesman problem is one of the most important problems in operations research, especially when additional precedence constraints are considered. Here, we consider the well-known variant where a linear order on k special vertices is given that has to be preserved in any feasible Hamiltonian cycle. This problem is called Ordered TSP and we consider it on input instances where the edge-cost function satisfies a β-relaxed triangle inequality, i.e., where the length of a direct edge cannot exceed the cost of any detour via a third vertex by more than a factor of β> 1. We design two new polynomial-time approximation algorithms for this problem. The first algorithm essentially improves over the best previously known algorithm for almost all values of k and β< 1.087889. The second algorithm gives a further improvement for 2n ≥ 11k + 7 and β< √³4/3 , where n is the number of vertices in the graph.