Abstract:
An efficient algorithm $\mathcal A$ with a guaranteed accuracy estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman routes) of maximal weight in a complete weighted undirected graph in a multidimensional Euclidean space $\mathbb R^k$. The complexity of the algorithm is $O(n^3)$. The number of traveling salesman routes for which the algorithm is asymptotically exact is established.