State of the art on approximating quadratic assignment problem I was wondering what is the state of the art on approximating the quadratic assignment problem (QAP). In particular, I am interested in the following instance. Suppose the $A = (a_{ij}) \in \{0,1\}^{n \times n}$ is the adjacency matrix of an undirected graph. Let $B = (b_{\ell k}) \in \mathbb{R}^{K \times K}$ and $\pi : [n] \to [K]$ be a map. (We might put some restriction on $\pi$ too, for example, equal number of nodes being mapped to each element of $[K]$.) We would like to solve
$$
\arg \max_{\pi} \sum_{ij} a_{ij} b_{\pi(i),\pi(j)}
$$
A more specific questions is this: what is known about semi-definite programming relaxations (SDP) of this problem? Are there ones which do not significantly increase the dimension of the problem? Any review papers on recent advancements?
See the following paper. There may have been other developments since then.

Maximum Quadratic Assignment Problem,
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko, 
ICALP 2010 

http://www.cs.princeton.edu/~kmakaryc/pdf/maxqap.pdf