Maximizing traveling salesman problem for special matrices

Abstract

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 α.