Gutin, Gregory and Yeo, Anders (2001) TSP tour domination and Hamilton cycle decompositions of regular digraphs.. Operations Research Letters, 28 (3).
Full text access: Open
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.
This is a Submitted version This version's date is: 2001 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/a836f503-4bc9-cc73-9d01-983ae86d6fa9/7/
Deposited by Research Information System (atira) on 18-Nov-2014 in Royal Holloway Research Online.Last modified on 18-Nov-2014