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, m atrices from M(n) and M(n, alpha) (alpha greater than or equal to 3) d efined 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 al pha max(/i-j/<not equal >1) w(ij). We describe an O(n)-algorithm solvi ng exactly the MTSP for matrices from M(n) and show that this algorith m 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 a t most n/(2 alpha(n - 1)). It is proved that the MTSP is NP-hard for m atrices from M(n, alpha) for every fixed positive alpha.