<p>See the following paper. There may have been other developments since then.</p>

<p>Maximum Quadratic Assignment Problem,
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko, 
ICALP 2010 </p>

<p><a href="http://www.cs.princeton.edu/~kmakaryc/pdf/maxqap.pdf" rel="nofollow">http://www.cs.princeton.edu/~kmakaryc/pdf/maxqap.pdf</a></p>

CC BY-SA 3.0
2014-12-14T09:46:02.420Z
this link is gone, but see http://arxiv.org/abs/1403.7721
Dima Pasechnik
CC BY-SA 3.0
2014-03-24T15:29:36.297Z
2014-03-24T15:29:36.297Z
Chandra Chekuri
<p>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?</p>

<approximation-algorithms><semidefinite-programming>
State of the art on approximating quadratic assignment problem
passerby51
# State of the art on approximating quadratic assignment problem

(Asked by: username_0 on 2014-03-24)

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?

**Tags:** approximation-algorithms, semidefinite-programming

---

## 1 answers

### Answer by username_1 on 2014-03-24. Score: 3 | Accepted answer

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>

> **Comments:**
> **username_2**: this link is gone, but see http://arxiv.org/abs/1403.7721  

---

