Well-solvable cases of the QAP with block-structured matrices
  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. 
Eranda \c{C}ela, Vladimir G. Deineko, Gerhard J. Woeginger
math.OC