Change search
ReferencesLink to record
Permanent link

Direct link
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
KTH, School of Computer Science and Communication (CSC).
2014 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 10, no 4, 18- p.Article in journal (Refereed) Published
Abstract [en]

We show that for every positive epsilon > 0, unless NP subset of BP QP, it is impossible to approximate the maximum quadratic assignment problem within a factor better than 2log(1-epsilon)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 - epsilon versus epsilon hard assuming the Unique Games Conjecture. Then, we present an O(root n)-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in state-of-the-art exact algorithms.

Place, publisher, year, edition, pages
2014. Vol. 10, no 4, 18- p.
Keyword [en]
Algorithms, Theory, Inapproximability, quadratic assignment problem
National Category
Computer Science Mathematics
URN: urn:nbn:se:kth:diva-156462DOI: 10.1145/2629672ISI: 000343962200002ScopusID: 2-s2.0-84906852643OAI: diva2:767370

QC 20141201

Available from: 2014-12-01 Created: 2014-11-28 Last updated: 2014-12-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Manokaran, Rajsekar
By organisation
School of Computer Science and Communication (CSC)
In the same journal
ACM Transactions on Algorithms
Computer ScienceMathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 12 hits
ReferencesLink to record
Permanent link

Direct link