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. Consider the linear recurrence: $F_{n+2} = F_{n+1} + F_{n}$ with $F_0 =0$ and $F_1 = 1$. In class, we saw that this can be written as

$\left(\begin{array}{c} F_{n+1} \\ F_{n} \end{array}\right) = \left(\begin{array}{c c}1 & 1 \\ 1 & 0 \end{array}\right)^n\cdot \left(\begin{array}{c} 1 \\ 0 \end{array}\right)$

Let us call the square matrix here $A$. We also showed that the eigenvalues $\lambda_1, \lambda_2$ of $A$ satisfies the equation $\det (A - I\lambda) = \lambda^2 - \lambda - 1 = 0$.