Mathematics – Combinatorics
Scientific paper
2001-04-24
Mathematics
Combinatorics
37 pages, 6 figures
Scientific paper
We obtain a number of results regarding the distribution of values of a quadratic function f on the set of nxn permutation matrices (identified with the symmetric group S_n) around its optimum (minimum or maximum). In particular, we estimate the fraction of permutations sigma such that f(sigma) lies within a given neighborhood of the optimal value of f. We identify some ``extreme'' functions f (there are 4 of those for n even and 5 for n odd) such that the distribution of every quadratic function around its optimum is a certain ``mixture'' of the distributions of the extremes and 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. In particular, we identify a large class of functions f with the property that permutations in the vicinity of 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) and 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.
Barvinok Alexander
Stephen Tamon
No associations
LandOfFree
The distribution of values in the quadratic assignment problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The distribution of values in the quadratic assignment problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The distribution of values in the quadratic assignment problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-648263