1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Computer Science, Royal Holloway, University of London
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