Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm

Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko

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.

Knowledge Graph



Sign up or login to leave a comment