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


| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.