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/8/12

Y1 - 2010/8/12

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 -