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 Haggkvist on the Hamilton decomposition of regular digraphs.
Operations Research Letters, 2001, Vol 28, Issue 3, p. 107-111
ATPS; Domination analysis; Hamilton cycle decompostion; Regular digraphs