Abstract (Gregory Gutin)
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.
Last modified: September 8, 1998.
Kim Skak Larsen
(kslarsen@imada.sdu.dk)