DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE ODENSE UNIVERSITY Domination Analysis in Combinatorial Optimization: probability, graphs and groups working together Gregory Gutin Department of Mathematics and Statistics Brunel University Thursday, September 24, 1998, at 4:15 PM The Seminar Room The domination number, dom(A,n), of an approximation algorithm for a combinatorial optimization problem is the maximum integer k=k(n) such that, for every instance I of size n of the problem A produces a solution x which is not worse than at least k solutions in I including x itself. We consider a fairly general (though, simple) algorithm that has factorial domination number for the traveling salesman and quadratic assignment problems. This, in particular, settles a conjecture by Glover and Punnen (1997). Probabilistic, graph-theoretical, group-theoretical and number-theoretical methods and results are used. This is joint work with Anders Yeo. Jørgen Bang-Jensen