Article ID: | iaor20011037 |
Country: | United States |
Volume: | 22 |
Issue: | 1 |
Start Page Number: | 13 |
End Page Number: | 17 |
Publication Date: | Feb 1998 |
Journal: | Operations Research Letters |
Authors: | Woeginger Gerhard J., Deineko V.G. |
Keywords: | programming: travelling salesman, matrices |
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.