The quadratic assignment problem is easy for robinsonian matrices

M. Laurent, M. Seminaroti

Research output: Contribution to journalArticleScientificpeer-review

13 Citations (Scopus)

Abstract

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
Volume43
Issue number1
DOIs
Publication statusPublished - Jan 2015

Keywords

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

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

  • Cite this