### 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 language | English |
---|---|

Pages (from-to) | 103-109 |

Journal | Operations Research Letters |

Volume | 43 |

Issue number | 1 |

DOIs | |

Publication status | Published - 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

Laurent, M., & Seminaroti, M. (2015). The quadratic assignment problem is easy for robinsonian matrices.

*Operations Research Letters*,*43*(1), 103-109. https://doi.org/10.1016/j.orl.2014.12.009