Deineko, Vladimir and Tiskin, Alexander (2006) One-sided monge TSP is NP-Hard. In: Gavrilova, M. and Gervasi, O. and Kumar, V. and Tan, C. J. K. and Taniar, D. and Lagana, A. and Mun, Y. and Choo, H., (eds.) Computational Science and Its Applications - ICCSA 2006. Lecture Notes in Computer Science, Volume 3982 . Springer, pp. 793-801. ISBN 9783540340751

PDF fulltext13.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (409Kb)

Request Changes to record.

Abstract

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 Mange 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, vie 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.

Item Type:	Book Item
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School
Series Name:	Lecture Notes in Computer Science
Publisher:	Springer
ISBN:	9783540340751
ISSN:	0302-9743
Book Title:	Computational Science and Its Applications - ICCSA 2006
Editor:	Gavrilova, M. and Gervasi, O. and Kumar, V. and Tan, C. J. K. and Taniar, D. and Lagana, A. and Mun, Y. and Choo, H.
Official Date:	2006
Dates:	Date Event 2006 Published
Volume:	Volume 3982
Number of Pages:	9
Page Range:	pp. 793-801
DOI:	10.1007/11751595_84
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	15 December 2015
Conference Paper Type:	Paper
Title of Event:	International Conference on Computational Science and Its Applications (ICCSA 2006)
Type of Event:	Conference
Location of Event:	Glasgow, Scotland
Date(s) of Event:	08 -11 May 2006

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item