MAXIMUM QUADRATIC ASSIGNMENT

• INSTANCE: Nonnegative symmetric $n\times n$ matrices A and B.

• SOLUTION: A permutation $\pi: [1..n]\rightarrow [1..n]$.

• MEASURE: $\sum_{i\ne j} a_{\pi(i),\pi(j)} b_{i,j}$.

  
  

• Bad News: At least as hard as MINIMUM TRAVELING SALESPERSON [31].

• Comment: If one of the matrices satisfies the triangle inequality, the problem is approximable within $4\sqrt 2$ [31].