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

被引：11

作者：

Cela, Eranda ^{[1
]}

Deineko, Vladimir G. ^{[2
]}

Woeginger, Gerhard J. ^{[3
]}

机构：

[1] Graz Univ Technol, Inst Optimierung & Diskrete Math, A-8010 Graz, Austria

[2] Univ Warwick, Warwick Business Sch, Coventry CV4 7AL, W Midlands, England

[3] TU Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands

来源：

DISCRETE APPLIED MATHEMATICS | 2015年 / 186卷

基金：

奥地利科学基金会;

关键词：

Combinatorial optimization; Computational complexity; Cut problem; Balanced cut; Monge condition; Product matrix; MONGE;

D O I：

10.1016/j.dam.2015.01.005

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：56 / 65

页数：10

共 16 条

[1]

[Anonymous], 2009, Assignment Problems, DOI DOI 10.1137/1.9780898717754

[2] The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases [J].