TSP tour domination and Hamilton cycle decompositions of regular digraphs.

Abstract

In this paper, we solve a problem by Glover and Punnen (J. Oper. Res. Soc. 48 (1997) 502–510) from the context of domination analysis, where the performance of a heuristic algorithm is rated by the number of solutions that are not better than the solution found by the algorithm, rather than by the relative performance compared to the optimal value. In particular, we show that for the asymmetric traveling salesman problem, there is a deterministic polynomial time algorithm that finds a tour that is at least as good as the median of all tour values. Our algorithm uses an unpublished theorem by Häggkvist on the Hamilton decomposition of regular digraphs.