TY - JOUR
T1 - Maximum quadratic assignment problem
T2 - Reduction from maximum label cover and LP-based approximation algorithm
AU - Makarychev, Konstantin
AU - Manokaran, Rajsekar
AU - Sviridenko, Maxim
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014/8
Y1 - 2014/8
N2 - We show that for every positive ε > 0, unless NP ∪ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2log1?ε 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 ? ε versus ε hard assuming the Unique Games Conjecture. Then, we present an O(√n)- approximation algorithm for the problem based on rounding of the linear programming relaxation often used in state-of-the-art exact algorithms.
AB - We show that for every positive ε > 0, unless NP ∪ BPQP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2log1?ε 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 ? ε versus ε hard assuming the Unique Games Conjecture. Then, we present an O(√n)- approximation algorithm for the problem based on rounding of the linear programming relaxation often used in state-of-the-art exact algorithms.
KW - Inapproximability
KW - Quadratic assignment problem
UR - http://www.scopus.com/inward/record.url?scp=84906852643&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906852643&partnerID=8YFLogxK
U2 - 10.1145/2629672
DO - 10.1145/2629672
M3 - Article
AN - SCOPUS:84906852643
SN - 1549-6325
VL - 10
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 4
M1 - 18
ER -