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