Gregory Gutin and Yeo, A. (2002) Polynomial approximation algorithms for the TSP and QAP with a factorial domination number. Discrete Applied Mathematics, 119 (1-2). pp. .
Full text access: Open
Glover and Punnen (J. Oper. Res. Soc. 48 (1997) 502) asked whether there exists a polynomial time algorithm that always produces a tour which is not worse than at least n!/p(n) tours for some polynomial p(n) for every TSP instance on n cities. They conjectured that, unless P=NP, the answer to this question is negative. We prove that the answer to this question is, in fact, positive. A generalization of the TSP, the quadratic assignment problem, is also considered with respect to the analogous question. Probabilistic, graph-theoretical, group-theoretical and number-theoretical methods and results are used.
This is a Published version This version's date is: 2002 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/9a192b34-c6c9-408e-7803-a1ef89b52a4e/1/
Deposited by () on 23-Dec-2009 in Royal Holloway Research Online.Last modified on 25-May-2010