Skip to main navigation Skip to search Skip to main content

Approximating the maximum quadratic assignment problem

  • Tel Aviv University
  • Aarhus University

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

In the maximum quadratic assignment problem, two nonnegative symmetric matrices are given and the objective is to compute a permutation. The problem is NP-hard and an indication to the hardness of approximating it, is that the best known approximation factors for maximum clustering with given sizes are 1/c when all sizes are equal to a constant c. An approximation algorithm with a constant performance guarantee under the assumption that the weights in B satisfy the triangle inequality.

Original languageEnglish
Pages (from-to)889-890
Number of pages2
JournalProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
DOIs
StatePublished - 2000

Fingerprint

Dive into the research topics of 'Approximating the maximum quadratic assignment problem'. Together they form a unique fingerprint.

Cite this