The Library
One-sided monge TSP is NP-Hard
Tools
Tools
Tools
Deineko, Vladimir and Tiskin, Alexander (2006) One-sided monge TSP is NP-Hard. In: International Conference on Computational Science and Its Applications (ICCSA 2006), Glasgow, SCOTLAND, MAY 08-AUG 11, 2006. Published in: COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 3, 3982 pp. 793-801.
Full text not available from this repository.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: | Conference Item (UNSPECIFIED) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Series Name: | LECTURE NOTES IN COMPUTER SCIENCE |
| Journal or Publication Title: | COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2006, PT 3 |
| Publisher: | SPRINGER-VERLAG BERLIN |
| ISBN: | 3-540-34075-0 |
| ISSN: | 0302-9743 |
| Editor: | Gavrilova, M and Gervasi, O and Kumar, V and Tan, CJK and Taniar, D and Lagana, A and Mun, Y and Choo, H |
| Date: | 2006 |
| Volume: | 3982 |
| Number of Pages: | 9 |
| Page Range: | pp. 793-801 |
| Identification Number: | 10.1007/11751595_84 |
| Publication Status: | Published |
| Title of Event: | International Conference on Computational Science and Its Applications (ICCSA 2006) |
| Location of Event: | Glasgow, SCOTLAND |
| Date(s) of Event: | MAY 08-AUG 11, 2006 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/33382 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
