The maximum Travelling Salesman Problem on symmetric Demidenko matrices

V.G. Deineko, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    8 Citations (Scopus)

    Abstract

    It is well-known that the Travelling Salesman Problem (TSP) is solvable in polynomial time, if the distance matrix fulfills the so-called Demidenko conditions. This paper investigates the closely related Maximum Travelling Salesman Problem (MaxTSP) on symmetric Demidenko matrices. Somewhat surprisingly, we show that — in strong contrast to the minimization problem — the maximization problem is NP-hard to solve. Moreover, we identify several special cases that are solvable in polynomial time. These special cases contain and generalize several predecessor results by Quintas and Supnick and by Kalmanson.
    Original languageEnglish
    Pages (from-to)413-425
    JournalDiscrete Applied Mathematics
    Volume99
    Issue number1-3
    DOIs
    Publication statusPublished - 2000

    Fingerprint

    Dive into the research topics of 'The maximum Travelling Salesman Problem on symmetric Demidenko matrices'. Together they form a unique fingerprint.

    Cite this