The quadratic assignment problem is easy for robinsonian matrices

M. Laurent; M. Seminaroti

doi:10.1016/j.orl.2014.12.009

The quadratic assignment problem is easy for robinsonian matrices

M. Laurent, M. Seminaroti

Research output: Contribution to journal › Article › Scientific › peer-review

19 Citations (Scopus)

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	https://doi.org/10.1016/j.orl.2014.12.009
Publication status	Published - Jan 2015

Keywords

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

Access to Document

10.1016/j.orl.2014.12.009

Cite this

@article{d3e9665fcbe34ed088fd85e062fb75a8,

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

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

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

year = "2015",

month = jan,

doi = "10.1016/j.orl.2014.12.009",

language = "English",

volume = "43",

pages = "103--109",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - The quadratic assignment problem is easy for robinsonian matrices

AU - Laurent, M.

AU - Seminaroti, M.

PY - 2015/1

Y1 - 2015/1

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

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

KW - quadratic assignment problem

KW - seriation

KW - Robinson (dis)similarity

KW - well solvable special case

U2 - 10.1016/j.orl.2014.12.009

DO - 10.1016/j.orl.2014.12.009

M3 - Article

SN - 0167-6377

VL - 43

SP - 103

EP - 109

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

The quadratic assignment problem is easy for robinsonian matrices

Abstract

Keywords

Access to Document

Fingerprint

Cite this