Efficient PTAS for the Maximum Traveling Salesman Problem in a Metric Space of Fixed Doubling Dimension

The maximum traveling salesman problem (Max TSP) is one of the intensively researched combinatorial optimization problems. It consists of finding a maximum-weight Hamiltonian cycle in a given complete weighted graph. This problem is APX-hard in the general and metric cases but admits approximation schemes in the geometric setting, when the vertices of the input graph are some points in fixed-dimensional real space and the edge weights are induced by some vector norm. In this paper, we propose the first polynomial-time approximation scheme for Max TSP in arbitrary metric space of fixed doubling dimension. In fact, the proposed algorithm implements a scheme EPTAS which, for any fixed $\varepsilon\in(0,1)$, finds a $(1-\varepsilon)$-approximate solution of the considered problem in cubic time. Also, we suggest a polynomial-time algorithm which computes asymptotically optimal solutions of the metric Max TSP in fixed and sublogarithmic doubling dimensions.