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-ε…