Abstract (Gregory Gutin)
Glover and Punnen (1997) 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).
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 (QAP), is also considered with
respect to the analogous question. Probabilistic, graph-theoretical and
group-theoretical methods and results are used.
This is joint work with A. Yeo.
Last modified: August 13, 1998.
Kim Skak Larsen
(kslarsen@imada.sdu.dk)