An asymptotically exact algorithm for the maximum traveling salesman problem in a finite-dimensional normed space

摘要

We consider the geometric maximum traveling salesman problem on assuming that the vertices of a graph lie in an arbitrary finite-dimensional normed space. For this problem we obtain an approximate algorithm with the relative error tending to zero as the number of vertices grows. The algorithm generalizes Serdyukov's algorithm for the Euclidean Max TSP.