On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space

Abstract

An efficient algorithm A with a guaranteed error estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman tours) of maximum weight in a complete weighted undirected graph in a multidimensional Euclidean space ℝ k . The time complexity of the algorithm is O(n 3). The number of traveling salesman tours for which the algorithm is asymptotically optimal is established.