TY - GEN
T1 - Maximum quadratic assignment problem
T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010
AU - Makarychev, Konstantin
AU - Manokaran, Rajsekar
AU - Sviridenko, Maxim
PY - 2010
Y1 - 2010
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-ε by a reduction from the maximum label cover problem. Then, we present an O(n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the 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-ε by a reduction from the maximum label cover problem. Then, we present an O(n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.
UR - http://www.scopus.com/inward/record.url?scp=77955320677&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77955320677&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-14165-2_50
DO - 10.1007/978-3-642-14165-2_50
M3 - Conference contribution
AN - SCOPUS:77955320677
SN - 3642141641
SN - 9783642141645
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 594
EP - 604
BT - Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
Y2 - 6 July 2010 through 10 July 2010
ER -