The approximate solution of the Euclidean traveling salesman problem on a CRAY X-MP (Q1112565)

Time necessary for exact solution of the traveling salesman problem is known to increase exponentially with the number of vertices. Therefore, in cases when finding any suboptimal solution is sufficient, it is desirable to have approximation algorithms which find a suboptimal solution in polynomial time. Of the many algorithms available, in the opinion of the author, a suitable candidate for parallelization is \textit{R. M. Sharp}'s partitioning algorithm [Math. Oper. Res. 2, 209-224 (1977; Zbl 0391.90091)]. The author describes clearly and in few words the essence and the way of its parallelization. The algorithm is implemented on a CRAY X-MP with two and four processors, and results using macrotasking and microtasking are presented.