This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Barvinok, A. Articles by Stephen, T. Search for Related Content

The Distribution of Values in the Quadratic Assignment Problem

Department of Mathematics, University of Michigan, 1858 East Hall, Ann Arbor, Michigan 48109-1109
Institute of Mathematics and Its Applications (IMA), University of Minnesota, 400 Lind Hall, 207 Church Street S.E., Minneapolis, Minnesota 55455-0436
barvinok(umich.edu
tamon(ima.umn.edu

We obtain a number of results regarding the distribution of values of a quadratic function f on the set of n x n permutation matrices (identified with the symmetric group S_n) around its optimum (minimum or maximum). We estimate the fraction of permutations such that f() 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 (which includes, for example, the objective function in the Traveling Salesman Problem) with a relative abundance of near-optimal permutations. Also, we identify a large 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). 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.

Key Words: Quadratic Assignment Problem; distribution; symmetric group; randomized algorithms; heuristics; representation theory
History: Received: July 17, 2001; revision received: October 9, 2002;