The distribution of values in the quadratic assignment problem
| dc.creator | Barvinok, Alexander | |
| dc.creator | Stephen, Tamon | |
| dc.date | 2001-04-24 | |
| dc.date.accessioned | 2026-07-07T04:41:26Z | |
| dc.date.available | 2026-07-07T04:41:26Z | |
| dc.description | 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. | |
| dc.description | 37 pages, 6 figures | |
| dc.identifier | https://arxiv.org/abs/math/0104229 | |
| dc.identifier | http://arxiv.org/abs/math/0104229 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/61358 | |
| dc.subject | Combinatorics | |
| dc.subject | 68R05 | |
| dc.title | The distribution of values in the quadratic assignment problem | |
| dc.type | text |