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

2014/02/14 by Eranda Çela, Çela, Eranda, Vladimir G. Deı̌neko +3 · 2 citations
Computer Science · Mathematics · #90B80 #Advanced Graph Theory Research #Commutative Algebra and Its Applications #FOS: Mathematics #G.1.6 #Optimization and Control (math.OC) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1402.3500

openalex publication_date 2014/02/14 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

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 respectively NP-hard.

Cited by

• Diamond transports in quadratic-form and distorted optimal transport
• A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization

Related

• New special cases of the Quadratic Assignment Problem with diagonally\n structured coefficient matrices
• On the Complexity of Some Facet-Defining Inequalities of the\n QAP-polytope
• The quadratic assignment problem is easy for Robinsonian matrices with\n Toeplitz structure
• Linearizable special cases of the QAP
• Equality of complexity classes P and NP: Linear programming formulation of the quadratic assignment problem