The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
arXiv:1407.2801
Abstract
We present a new polynomially solvable case of the Quadratic Assignment Problem in Koopmans-Beckman form , by showing that the identity permutation is optimal when and are respectively a Robinson similarity and dissimilarity matrix and one of or is a Toeplitz matrix. A Robinson (dis)similarity matrix is a symmetric matrix whose entries (increase) decrease monotonically along rows and columns when moving away from the diagonal, and such matrices arise in the classical seriation problem.
15 pages, 2 figures