Maximum quadratic assignment problem: Reduction from maximum label cover and LP-based approximation algorithm

Konstantin Makarychev*, Rajsekar Manokaran, Maxim Sviridenko

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
Pages594-604
Number of pages11
EditionPART 1
DOIs
StatePublished - Aug 12 2010
Event37th International Colloquium on Automata, Languages and Programming, ICALP 2010 - Bordeaux, France
Duration: Jul 6 2010Jul 10 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6198 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other37th International Colloquium on Automata, Languages and Programming, ICALP 2010
CountryFrance
CityBordeaux
Period7/6/107/10/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Maximum quadratic assignment problem: Reduction from maximum label cover and LP-based approximation algorithm'. Together they form a unique fingerprint.

Cite this