Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm
verfasst von : Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show that for every positive
ε
> 0, unless
${\mathcal NP} \subset {\mathcal BPQP}$
, it is impossible to approximate the maximum quadratic assignment problem within a factor better than
$2^{\log^{1-\varepsilon} n}$
by a reduction from the maximum label cover problem. Then, we present an
$O(\sqrt{n})$
-approximation algorithm for the problem based on rounding of the linear programming relaxation often used in the state of the art exact algorithms.