Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
One-sided monge TSP Is NP-hard. / Deineko, Vladimir; Tiskin, Alexander.
Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006). 2006. p. 793-801 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3982).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
}
TY - GEN
T1 - One-sided monge TSP Is NP-hard
AU - Deineko, Vladimir
AU - Tiskin, Alexander
PY - 2006/1/1
Y1 - 2006/1/1
N2 - The Travelling Salesman Problem (TSP) is a classical NP-hard optimisation problem. There exist, however, special cases of the TSP that can be solved in polynomial time. Many of the well-known TSP special cases have been characterized by imposing special four-point conditions on the underlying distance matrix. Probably the most famous of these special cases is the TSP on a Monge matrix, which is known to be polynomially solvable (as are some other generally NP-hard problems restricted to this class of matrices). By relaxing the four-point conditions corresponding to Monge matrices in different ways, one can define other interesting special cases of the TSP, some of which turn out to be polynomially solvable, and some NP-hard. However, the complexity status of one such relaxation, which we call one-sided Monge TSP (also known as the TSP on a relaxed Supnick matrix), has remained unresolved. In this note, we show that this version of the TSP problem is NP-hard. This completes the full classification of all possible four-point conditions for symmetric TSP. © Springer-Verlag Berlin Heidelberg 2006.
AB - The Travelling Salesman Problem (TSP) is a classical NP-hard optimisation problem. There exist, however, special cases of the TSP that can be solved in polynomial time. Many of the well-known TSP special cases have been characterized by imposing special four-point conditions on the underlying distance matrix. Probably the most famous of these special cases is the TSP on a Monge matrix, which is known to be polynomially solvable (as are some other generally NP-hard problems restricted to this class of matrices). By relaxing the four-point conditions corresponding to Monge matrices in different ways, one can define other interesting special cases of the TSP, some of which turn out to be polynomially solvable, and some NP-hard. However, the complexity status of one such relaxation, which we call one-sided Monge TSP (also known as the TSP on a relaxed Supnick matrix), has remained unresolved. In this note, we show that this version of the TSP problem is NP-hard. This completes the full classification of all possible four-point conditions for symmetric TSP. © Springer-Verlag Berlin Heidelberg 2006.
UR - http://www.scopus.com/inward/record.url?scp=33745880379&partnerID=8YFLogxK
U2 - 10.1007/11751595_84
DO - 10.1007/11751595_84
M3 - Conference contribution
AN - SCOPUS:33745880379
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 793
EP - 801
BT - Computational Science and Its Applications - ICCSA 2006 (ICCSA 2006)
ER -
ID: 127757242