TY - JOUR
T1 - The maximum Travelling Salesman Problem on symmetric Demidenko matrices
AU - Deineko, V.G.
AU - Woeginger, G.J.
PY - 2000
Y1 - 2000
N2 - 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.
AB - 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.
U2 - 10.1016/S0166-218X(99)00148-1
DO - 10.1016/S0166-218X(99)00148-1
M3 - Article
SN - 0166-218X
VL - 99
SP - 413
EP - 425
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 1-3
ER -