Algebraic and Topological Combinatorics

Special Session at the Fall Eastern Section Meeting
of the American Mathematical Society

Williams College, Williamstown, MA
October 13-14, 2001



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:



Back to the mainpage.
last updated: August 21, 2001