# The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure

arXiv: https://arxiv.org/abs/1407.2801 · HTML: https://mlsanity.com/paper/1407.2801/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2014.

## Built on by (most cited first, 1 of 1)

- [Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT instances](https://mlsanity.com/paper/2403.02783/) (2024)

## Abstract (arXiv)

We present a new polynomially solvable case of the Quadratic Assignment Problem in Koopmans-Beckman form QAP(A,B), by showing that the identity permutation is optimal when A and B are respectively a Robinson similarity and dissimilarity matrix and one of A or B 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.