Maximizing traveling salesman problem for special matrices

The authors consider the maximizing travelling salesman problem (MTSP) for two special classes of matrices with non-negative entries, namely, matrices from M(n) and defined as follows. An matrix if for all i, j such that . An matrix if . They 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 for with a relative error of at most . It is proved that the MTSP is NP-hard for matrices from for every fixed positive .