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.
翻译:最大的旅行推销员问题(Max~TSP)包括找到一个汉密尔顿周期,其边缘在给定的完整加权图中的总重量最大。 我们证明,当边缘重量由一个捆绑的双倍尺寸的公制空间引领时,简单的贪婪补丁型可以找到非现最佳的解决问题的办法。以最大重量周期覆盖为起点,这种超常迭代式的循环组合可以将每个步骤的重量损失减少到最小。