  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. We prove that, in the case when the edge weights are
induced by a metric space of bounded doubling dimension, asymptotically optimal
solutions of the problem can be found by the simple greedy patching heuristic.
Taking as a start point a maximum-weight cycle cover, this heuristic
iteratively patches pairs of its cycles into one minimizing the weight loss at
each step.
