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.

Original language | English |
---|

Publisher | s.n. |
---|

Number of pages | 16 |
---|

Publication status | Published - 2014 |
---|

Name | arXiv |
---|

Volume | 1402.3500 [math.OC] |
---|