Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP

J. Cirasella, D.S. Johnson, L.A. McGeoch, W. Zhang, The asymmetric traveling salesman problem: algorithms, instance generators and tests, Proceedings of third Workshop on Algorithm Engineering and Experiments (ALENEX 01), Washington DC, 2001, to appear.

Glover, 2001, Construction heuristics for the asymmetric traveling salesman problem, European J. Oper. Res., 129, 555, 10.1016/S0377-2217(99)00468-3

Glover, 1997, The traveling salesman problem: new solvable cases and linkages with the development of approximation algorithms, J. Oper. Res. Soc., 48, 502, 10.1057/palgrave.jors.2600392

G. Gutin, A. Yeo, Polynomial approximation algorithms for the TSP and the QAP with factorial domination number, Discrete Appl. Math., to appear.

G. Gutin, A. Yeo, TSP tour domination and Hamilton cycle decomposition of regular digraphs, Oper. Res. Lett., to appear.

G. Gutin, A. Zverovich, Evaluation of the Contract-or-Patch Heuristic for the Asymmetric TSP, submitted for publication.

D.S. Johnson, L.A. McGeoch, The traveling salesman problem: a case study in local optimization. in: E.H.L. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization, Wiley, New York, 1997, 215–310.

A.P. Punnen, S. Kabadi, Domination analysis of some heuristics for the asymmetric traveling salesman problem, submitted.

G. Reinelt, The Traveling Salesman Problem: Computational Solutions for TSP Applications Springer Lecture Notes in Computer Science 840, 1994, Springer-Verlag, Berlin.