MAXIMIZING TRAVELING SALESMAN PROBLEM FOR SPECIAL MATRICES

We consider the maximizing travelling salesman problem (MTSP) for two special classes of n x n matrices with non-negative entries, namely, matrices from M(n) and M(n, alpha) (alpha greater than or equal to 3) defined as follows. An n x n matrix W = [w(ij)] epsilon M(n) if w(ij) = 0 for all i,j such that /i-j/not equal 1. An n x n matrix W = [w(ij)] epsilon M(n, alpha) if min(/i-j/=1) w(ij) greater than or equal to alpha max(/i-j/<not equal >1) w(ij). 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, alpha) for alpha greater than or equal to 3 with a relative error of at most n/(2 alpha(n - 1)). It is proved that the MTSP is NP-hard for matrices from M(n, alpha) for every fixed positive alpha.