DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                              ODENSE UNIVERSITY                              

                Polynomial Algorithms for the TSP and the QAP                
                      with a Factorial Domination Number                     

                                Gregory Gutin                                
                   Department of Mathematics and Statistics                  
                              Brunel University                              

                    Tuesday, September 8, 1998, at 2:15 PM                   
                               The Seminar Room                              


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.


                                                          Jørgen Bang-Jensen