Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover   and LP-based Approximation Algorithm
  We show that for every positive $\epsilon > 0$, unless NP $\subset$ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than $2^{\log^{1-\epsilon} n}$ by a reduction from the maximum label cover problem. Our result also implies that Approximate Graph Isomorphism is not robust and is in fact, $1 - \epsilon$ vs $\epsilon$ hard assuming the Unique Games Conjecture.   Then, we present an $O(\sqrt{n})$-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms. 
Konstantin Makarychev and Rajsekar Manokaran and Maxim Sviridenko
cs.CC cs.DS