  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.
