= Quadratic assignment problem
{title2=$\min_\pi\sum_{i\ne j}a_{ij}b_{\pi(i),\pi(j)}$}
= QAP
{c}
{synonym}
A <permutation> assigns facilities to locations, and the objective combines their pairwise interactions with pairwise location costs. Ordered-pair and unordered-pair conventions differ by a factor of two for symmetric data. The decision version is <NP-complete>: letting $A$ record a directed cycle makes the objective exactly the length of a <travelling salesman problem> tour under the ordering given by the <permutation>. The optimization version is <NP-hard>.
Back to article page
