The maximum travelling salesman problem on symmetric Demidenko matrices

The maximum travelling salesman problem on symmetric Demidenko matrices

0.00 Avg rating0 Votes
Article ID: iaor20012983
Country: Netherlands
Volume: 99
Issue: 1/3
Start Page Number: 413
End Page Number: 425
Publication Date: Feb 2000
Journal: Discrete Applied Mathematics
Authors: ,
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 (Max TSP) 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.

Reviews

Required fields are marked *. Your email address will not be published.