scientific article; zbMATH DE number 1985298
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].
- The asymptotic behaviour of quadratic sum assignment problems: A statistical mechanics approach
- Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach
- The use of the ``golden section rule in probability modeling algorithms.
- Stochastic Analysis of the Quadratic Assignment Problem
- Autocorrelation measures for the quadratic assignment problem
- The distribution of values in the quadratic assignment problem
- The Distribution of Values in the Quadratic Assignment Problem
- The random quadratic assignment problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429162)