### 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 language | English |
---|---|

Pages (from-to) | 56-65 |

Number of pages | 10 |

Journal | Discrete Applied Mathematics |

Volume | 186 |

DOIs | |

Publication status | Published - 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

Çela, E., Deineko, V. G., & Woeginger, G. J. (2015). Well-solvable cases of the QAP with block-structured matrices.

*Discrete Applied Mathematics*,*186*, 56-65. https://doi.org/10.1016/j.dam.2015.01.005