The University of Michigan Combinatorics Seminar
Fall 2001
September 14, 4:10-5:00, 3866 East Hall

The distribution of values in the quadratic assignment problem

Tamon Stephen

University of Michigan


We obtain a number of results regarding the distribution of values of a quadratic function f on the set of n by n permutation matrices (identified with the symmetric group Sn) around its optimum (minimum or maximum). We estimate the fraction of permutations w such that f(w) lies within a given neighborhood of the optimal value of f and relate the optimal value with the average value of f over a neighborhood of the optimal permutation.

We describe a natural class of functions f with the property that permutations close to the optimal permutation in the Hamming metric of Sn tend to produce near optimal values of f (such is, for example, the objective function in the symmetric Traveling Salesman Problem). Also, we show that for general f, just the opposite behavior may take place: an average permutation in the vicinity of the optimal permutation may be much worse than an average permutation in the whole group Sn.

This is joint work with Alexander Barvinok.