The traveling salesman problem with precedence constraints is one of the most important problems in operations research. 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 problems. The first algorithm essentially improves over the best previously known algorithm for almost all values of k and β ＜ 1.12651. The second algorithm gives a further improvement for 2n ≥ 11k + 7 and β ＜ 2/~3(1/2), where n is the number of vertices in the graph.
展开▼
