No label defined (Q4429162)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1985298
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1985298 |
Statements
24 September 2003
0 references
quadratic assignment
0 references
distribution of values
0 references
combinatorial optimization
0 references
0.9184626340866088
0 references
0.9170894622802734
0 references
0.8580975532531738
0 references
0.8354767560958862
0 references
0.8354767560958862
0 references
The quadratic assignment problem QAP is given by two \(n\times n\) matrices \(A\), \(B\); the objective function is the trace of \(AB^t:\sum a_{ij} b_{ij}\). The goal is to maximize (or minimize) \(f(s)= \sum b_{s(i)s(j)}a_{ij}\) over \(s\in S_n\), the symmetric group. The symmetric traveling salesman problem is a special case of the symmetric QAP. The mean value \(\overline f\) can be computed easily (by products of the sums of the diagonal elements resp. off-diagonal elements) as well as the variance, too. Let \(t\) be an optimal permutation. The questions the authors are concerned with are -- given a constant \(0< g< 1\), how many permutations \(s\in S_n\) satisfy \(f(s)-\overline f\geq g(f(t)-\overline f)\)? -- how far away (with respect to the Hamming distance) from \(t\) are ``good'' permutations? The authors prove several interesting results and give some evidence and explanation, why the general QAP is computationally hard. For the entire collection see [Zbl 1013.00014].
0 references