Quadratic assignment problem (${\min }_{\pi }{\sum }_{i\ne j}{a}_{ij}{b}_{\pi (i),\pi (j)}$)

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.

For each facility $i$ and location $k$, independently minimize its row contribution over bijections from the other facilities to the other locations, giving ${\ell }_{ik}$. Every complete assignment has row contribution at least its corresponding ${\ell }_{ik}$, so minimizing their sum is a lower bound on the quadratic objective. Fixed assignments are retained as constraints in this assignment problem, which the Hungarian algorithm solves. The independently optimal rows need not be simultaneously realizable, explaining why the bound can be strict.