Well-solvable cases of the QAP with block-structured matrices

E. Çela, V.G. Deineko, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
1 Downloads (Pure)

Abstract

We investigate special cases of the quadratic assignment problem (QAP) where one of the two underlying matrices carries a simple block structure. For the special case where the second underlying matrix is a monotone anti-Monge matrix, we derive a polynomial time result for a certain class of cut problems. For the special case where the second underlying matrix is a product matrix, we identify two sets of conditions on the block structure that make this QAP polynomially solvable and NP-hard, respectively. Keywords: Combinatorial optimization; Computational complexity; Cut problem; Balanced cut; Monge condition; Product matrix
Original languageEnglish
Pages (from-to)56-65
Number of pages10
JournalDiscrete Applied Mathematics
Volume186
DOIs
Publication statusPublished - 2015

Fingerprint Dive into the research topics of 'Well-solvable cases of the QAP with block-structured matrices'. Together they form a unique fingerprint.

  • Cite this