  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.
