Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418916 | Discrete Applied Mathematics | 2015 | 10 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Eranda Çela, Vladimir G. Deineko, Gerhard J. Woeginger,