scientific article; zbMATH DE number 1985298

From MaRDI portal
Publication:4429162





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].











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)