The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
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.
|, , ,|
|Operations Research Letters|
|Mixed-Integer Nonlinear Optimization|
|Organisation||Networks and Optimization|
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).