论文标题
欧几里得旅行推销员问题的2-OPT启发式术的近似比
The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem
论文作者
论文摘要
2-OPT启发式是针对旅行推销员问题的简单改进启发式方法。它从任意之旅开始，然后反复用另外两个边缘取代游览的两个边缘，只要这会缩短巡回演出即可。我们将证明，对于$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n的欧几里得旅行推销员问题，2-opt启发式的近似值为$θ（\ log n/ \ log log \ log \ log n）$。这改善了Chandra，Karloff和Tove [3]在1999年给出的$ O（\ log n $）的上限。
The 2-Opt heuristic is a simple improvement heuristic for the Traveling Salesman Problem. It starts with an arbitrary tour and then repeatedly replaces two edges of the tour by two other edges, as long as this yields a shorter tour. We will prove that for Euclidean Traveling Salesman Problems with $n$ cities the approximation ratio of the 2-Opt heuristic is $Θ(\log n/ \log \log n)$. This improves the upper bound of $O(\log n$) given by Chandra, Karloff, and Tovey [3] in 1999.
