A solvable case of the quadratic assignment problem

V.G. Deineko, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    20 Citations (Scopus)


    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 languageEnglish
    Pages (from-to)13-17
    Number of pages5
    JournalOperations Research Letters
    Issue number1
    Publication statusPublished - 1998


    Dive into the research topics of 'A solvable case of the quadratic assignment problem'. Together they form a unique fingerprint.

    Cite this