The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases

R.E. Burkard, E. Çela, G. Rote, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    35 Citations (Scopus)
    1 Downloads (Pure)

    Abstract

    This paper investigates a restricted version of the Quadratic Assignment Problem (QAP), where one of the coefficient matrices is an Anti-Monge matrix with non-decreasing rows and columns and the other coefficient matrix is a symmetric Toeplitz matrix. This restricted version is called the Anti-Monge—Toeplitz QAP. There are three well-known combinatorial problems that can be modeled via the Anti-Monge—Toeplitz QAP: (Pl) The Turbine Problem, i.e. the assignment of given masses to the vertices of a regular polygon such that the distance of the center of gravity of the resulting system to the center of the polygon is minimized. (P2) The Traveling Salesman Problem on symmetric Monge distance matrices. (P3) The arrangement of data records with given access probabilities in a linear storage medium in order to minimize the average access time. We identify conditions on the Toeplitz matrixB that lead to a simple solution for the Anti-Monge—Toeplitz QAP: The optimal permutation can be given in advance without regarding the numerical values of the data. The resulting theorems generalize and unify several known results on problems (P1), (P2), and (P3). We also show that the Turbine Problem is NP-hard and consequently, that the Anti-Monge—Toeplitz QAP is NP-hard in general.
    Original languageEnglish
    Pages (from-to)125-158
    Number of pages34
    JournalMathematical Programming
    Volume82
    Issue number1-2
    DOIs
    Publication statusPublished - 1998

    Fingerprint

    Dive into the research topics of 'The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: easy and hard cases'. Together they form a unique fingerprint.

    Cite this