of the American Mathematical Society

Tamon M. Stephen

(University of Michigan)

## The Distribution of Values in The Quadratic Assignment Problem

Abstract[ps] [pdf]:We obtain a number of results regarding the distribution of values of a quadratic function $f$ on the set of $n \times n$ permutation matrices (identified with the symmetric group $S_n$) around its optimum (minimum or maximum). We estimate the fraction of permutations $\sigma$ such that $f(\sigma)$ 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 $S_n$ 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 $S_n$.

This is joint work with Alexander Barvinok.

Related material:

- Alexander Barvinok, Tamon M. Stephen

The Distribution of Values in The Quadratic Assignment Problem

Back to the mainpage.

last updated: August 21, 2001