The quadratic assignment problem is easy for robinsonian matrices

M. Laurent, M. Seminaroti

Research output: Contribution to journalArticleScientificpeer-review

18 Citations (Scopus)


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 AA and BB are respectively a Robinson similarity and dissimilarity matrix and one of AA or BB 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.
Original languageEnglish
Pages (from-to)103-109
JournalOperations Research Letters
Issue number1
Publication statusPublished - Jan 2015


  • quadratic assignment problem
  • seriation
  • Robinson (dis)similarity
  • well solvable special case


Dive into the research topics of 'The quadratic assignment problem is easy for robinsonian matrices'. Together they form a unique fingerprint.

Cite this