Abstract
This short note investigates a restricted version of the quadratic assignment problem (QAP), where one of the coefficient matrices is a Kalmanson matrix, and where the other coefficient matrix is a symmetric circulant matrix that is generated by a decreasing function. This restricted version is called the Kalmanson-circulant QAP. We prove that – in strong contrast to the general QAP – this version can be solved easily. Our result naturally generalizes a well-known theorem of Kalmanson on the travelling salesman problem.
| Original language | English |
|---|---|
| Pages (from-to) | 13-17 |
| Number of pages | 5 |
| Journal | Operations Research Letters |
| Volume | 22 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1998 |
Fingerprint Dive into the research topics of 'A solvable case of the quadratic assignment problem'. Together they form a unique fingerprint.
Cite this
Deineko, V. G., & Woeginger, G. J. (1998). A solvable case of the quadratic assignment problem. Operations Research Letters, 22(1), 13-17. https://doi.org/10.1016/S0167-6377(97)00047-3