论文标题
贪婪的启发式启发式启发式的最大tsp的渐近最优性在双倍指标中
Asymptotic Optimality of the Greedy Patching Heuristic for Max TSP in Doubling Metrics
论文作者
论文摘要
最大旅行人员问题（Max〜TSP）包括找到一个汉密尔顿周期，在给定的完整加权图中，边缘的总重量最大。我们证明，在边缘权重通过有界加倍维度的度量空间引起的情况下，可以通过简单的贪婪斑点启发式启发式找到问题的渐近最佳解决方案。作为起点，最大重量循环盖，这种启发式迭代将其循环对成对贴上一个最小化的体重减轻。
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.
