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 language | English |
|---|---|
| Pages (from-to) | 889-890 |
| Number of pages | 2 |
| Journal | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
| DOIs | |
| State | Published - 2000 |
Fingerprint
Dive into the research topics of 'Approximating the maximum quadratic assignment problem'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver