Maximum Quadratic Assignment
January 28, 2009
Quadratic Assignment is a basic problem in combinatorial optimization, which generalizes several other problems such as Traveling Salesman, Linear Arrangement, and Dense-$k$-Subgraph. The input to the Maximum Quadratic
Assignment Problem consists of two $n \times n$ symmetric non-negative matrices $W=(w_{i,j})$ and $D=(d_{i,j})$, and the goal is to find a permutation $P$ on $[n]$ that maximizes the sum over all $(i,j)$ of $w_{i,j} \times d_{P(i),P(j)}$. We give
an $\tildeO(\sqrt{n})$ approximation algorithm, which is the first non-trivial approximation guarantee for this problem. When one of the matrices $W$ or $D$ satisfies triangle inequality, we obtain a 3.16 approximation algorithm, which improves over the previously best-known guarantee of 4.
This is joint work with Maxim Sviridenko.
This is joint work with Maxim Sviridenko.