Blokh, D. and Gutin, Gregory (1995) Maximizing traveling salesman problem for special matrices. Discrete Applied Mathematics, 56 (1).
Full text access: Open
We consider the maximizing travelling salesman problem (MTSP) for two special classes of n × n matrices with non-negative entries, namely, matrices from M(n) and M(n, α) (α 3) defined as follows. An n × n matrix W = [wij]M(n) if wij = 0 for all i, j such that ¦i – j¦ ≠ 1. An n × n matrix W = [wij]M(n, α) if min¦i-j¦ = 1 wijαmax¦i-j¦ ≠ 1 wij. We describe an O(n)- algorithm solving exactly the MTSP for matrices from M (n) and show that this algorithm provides an approximate solution of the MTSP for matrices from M(n, α) for α 3 with a relative error of at most n/(2α(n – 1)). It is proved that the MTSP is NP-hard for matrices from M(n, α) for every fixed positive α.
This is a Submitted version This version's date is: 1995 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/c16589de-e4ba-c1fa-aadc-b744b18ef89f/3/
Deposited by Research Information System (atira) on 01-Jun-2012 in Royal Holloway Research Online.Last modified on 01-Jun-2012