2014-12-01
The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
Publication
Publication
Operations Research Letters
,
Volume available onlin
-
Issue 18 December 2014
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.
| Additional Metadata | |
|---|---|
| Keywords | quadratic assignment, polynomial time algorithm, Robinson matrix, seriation problem |
| THEME | Logistics (theme 3) |
| Publisher | North-Holland |
| Journal | Operations Research Letters |
| Project | Mixed-Integer Nonlinear Optimization |
| Note | Published paper: DOI: 10.1016/j.orl.2014.12.009 |
| Grant | This work was funded by the European Commission 7th Framework Programme; grant id h2020/764759 - Mixed-Integer Non-Linear Optimisation Applications (MINOA) |
| Citation |
Laurent, M, & Seminaroti, M. (2014). The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure. Operations Research Letters, available onlin(18 December 2014).
|
