A solvable case of the quadratic assignment problem

A solvable case of the quadratic assignment problem

0.00 Avg rating0 Votes
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: ,
Keywords: programming: travelling salesman, matrices
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.

Reviews

Required fields are marked *. Your email address will not be published.