algorithm - 证明 TSP 度量的近似

Question

我遇到了以下问题:

考虑以下启发式:从仅包含一个顶点的游览开始。在每一步中，找到游览之外的顶点，该顶点与游览的某个顶点的距离更短。令 v 为外顶点，u 为内顶点。在游览中紧跟在 u 之后添加 v。假设您的边遵循三角形距离属性。我们如何证明该启发式算法是 TSP 度量问题的 2 近似值？

有人知道如何开始吗？

提前致谢

Answer 1

显然，无法证明所描述的算法不是 2 近似。 Wikipedia article提到出版物

丹尼尔·J·罗森克兰茨；斯特恩斯，理查德 E.； Lewis, Philip M., II (1977)，“旅行商问题的几种启发式分析”，SIAM Journal on Computing 6 (5): 563–581, doi:10.1137/0206041

其中显然作者表明最近邻启发式算法产生了 Theta( log n ) 的近似比率，其中 n 是位置数，即使实例满足三角不等式:

Rosenkrantz et al. [1977] showed that the NN algorithm has the approximation factor Theta(log|V|) for instances satisfying the triangle inequality.

但是，OP 可能描述了不同的算法；不同贪心启发式算法的逼近率分析可以在下面的文章中找到。

SIAM Journal on Computing, 1977, Vol. 6, No. 3 : pp. 563-581 An Analysis of Several Heuristics for the Traveling Salesman Problem Rosenkrantz, D., Stearns, R., and Lewis, II, P. (doi: 10.1137/0206041)