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

      0 references
      0 references
      24 September 2003
      0 references
      quadratic assignment
      0 references
      distribution of values
      0 references
      combinatorial optimization
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references