We show that for every positive ε > 0, unless NP is contained in BVQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2~(log 1-ε) by a reduction from the maximum label cover problem. Then, we present an O(n~(2/1))-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.
展开▼
