A solvable case of the quadratic assignment problem

V.G. Deineko, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    20 Citations (Scopus)

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

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

  • Cite this