@book{a83ca1a7659343dfbec58cb6843eb3e5,

title = "The Quadratic Assignment Problem is Easy for Robinsonian Matrices",

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 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.",

keywords = "quadratic assignment problem, Robinson (dis)similarity, seriation, well solvable special case",

author = "M. Laurent and M. Seminaroti",

year = "2014",

month = jul,

day = "10",

language = "English",

volume = "1407.2801",

series = "Preprint at arXiv",

publisher = "Cornell University Library",

}