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: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    8 Citations (Scopus)

    Abstract

    The Anti-Monge-Toeplitz QAP (AMT-QAP) is a restricted version of the Quadratic Assignment Problem (QAP), with a monotone Anti-Monge matrix and a symmetric Toeplitz matrix. The following problems can be modeled via the AMT-QAP: (P1) The Turbine Problem, i. e. the assignment of given masses to the vertices of a regular polygon such that the distance of the gravity center of the resulting system to the polygon's center is minimized. (P2) The Traveling Salesman Problem on symmetric Monge matrices. (P3) The linear arrangement of records with given access probabilities in order to minimize the average access time. We identify conditions on the Toeplitz matrix that lead to polynomially solvable cases of the AMT-QAP. In each of these cases an optimal permutation can be given without regarding the numerical problem data. We show that the Turbine Problem is NP-hard and consequently, that the AMT-QAP is NP-hard.
    Original languageEnglish
    Title of host publicationInteger Programming and Combinatorial Optimization (Proceedings 5th International IPCO Conference, Vancouver BC, Canada, June 3-5, 1996)
    EditorsW.H. Cunningham, S.T. McCormick, M. Queyranne
    Place of PublicationBerlin
    PublisherSpringer
    Pages204-218
    ISBN (Print)3-540-61310-2
    DOIs
    Publication statusPublished - 1996

    Publication series

    NameLecture Notes in Computer Science
    Volume1084
    ISSN (Print)0302-9743

    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