Efficient PTAS for the Maximum Traveling Salesman Problem in a Metric Space of Fixed Doubling Dimension
share
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 ε∈(0,1), finds a (1-ε)-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.
READ FULL TEXT