The Quadratic Assignment Problem is Easy for Robinsonian Matrices

M. Laurent, M. Seminaroti

Research output: Book/ReportReportProfessional

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.
Original languageEnglish
Place of PublicationIthaca
PublisherCornell University Library
Number of pages14
Volume1407.2801
Publication statusPublished - 10 Jul 2014

Publication series

NamePreprint at arXiv
Volume1407.2801v1

Fingerprint

Quadratic Assignment Problem
Seriation
Toeplitz matrix
Dissimilarity
Symmetric matrix
Permutation
Decrease
Similarity

Keywords

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

Cite this

Laurent, M., & Seminaroti, M. (2014). The Quadratic Assignment Problem is Easy for Robinsonian Matrices. (Preprint at arXiv; Vol. 1407.2801v1). Ithaca: Cornell University Library.
Laurent, M. ; Seminaroti, M. / The Quadratic Assignment Problem is Easy for Robinsonian Matrices. Ithaca : Cornell University Library, 2014. 14 p. (Preprint at arXiv).
@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 = "7",
day = "10",
language = "English",
volume = "1407.2801",
series = "Preprint at arXiv",
publisher = "Cornell University Library",

}

Laurent, M & Seminaroti, M 2014, 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.

Ithaca : Cornell University Library, 2014. 14 p. (Preprint at arXiv; Vol. 1407.2801v1).

Research output: Book/ReportReportProfessional

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 -

Laurent M, Seminaroti M. The Quadratic Assignment Problem is Easy for Robinsonian Matrices. Ithaca: Cornell University Library, 2014. 14 p. (Preprint at arXiv).