### Abstract

Original language | English |
---|---|

Place of Publication | Ithaca |

Publisher | Cornell University Library |

Number of pages | 14 |

Volume | 1407.2801 |

Publication status | Published - 10 Jul 2014 |

### Publication series

Name | Preprint at arXiv |
---|---|

Volume | 1407.2801v1 |

### Fingerprint

### Keywords

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

### Cite this

*The Quadratic Assignment Problem is Easy for Robinsonian Matrices*. (Preprint at arXiv; Vol. 1407.2801v1). Ithaca: Cornell University Library.

}

*The Quadratic Assignment Problem is Easy for Robinsonian Matrices*. Preprint at arXiv, vol. 1407.2801v1, vol. 1407.2801, Cornell University Library, Ithaca.

**The Quadratic Assignment Problem is Easy for Robinsonian Matrices.** / Laurent, M.; Seminaroti, M.

Research output: Book/Report › Report › Professional

TY - BOOK

T1 - The Quadratic Assignment Problem is Easy for Robinsonian Matrices

AU - Laurent, M.

AU - Seminaroti, M.

PY - 2014/7/10

Y1 - 2014/7/10

N2 - 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.

AB - 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.

KW - quadratic assignment problem

KW - Robinson (dis)similarity

KW - seriation

KW - well solvable special case

M3 - Report

VL - 1407.2801

T3 - Preprint at arXiv

BT - The Quadratic Assignment Problem is Easy for Robinsonian Matrices

PB - Cornell University Library

CY - Ithaca

ER -