Arora Algorithm 0 Review and References

发表于 更新于 分类于 ， 阅读次数：

Arora算法, 简述及参考资料.

Arora算法是欧氏空间TSP的PTAS算法, 见Arora (1998). 给定顶点个数为\(n\)的TSP实例, 对任意的\(\epsilon>0\), 该算法可以在\(n^{O(1/\epsilon)}\)的时间内找到\((1+\epsilon)\)近似的解, 之后此时间复杂度又被改进至\(n(\log n)^{O(1/\epsilon)}\). (Mitchell在之后也独立发现了类似的时间复杂度为\(n^{O(1/\epsilon)}\)的PTAS算法, 见Mitchell (1999).

算法的具体步骤如下:

  1. 顶点扰动并调节比例;
  2. 使用网格线随机分割包含该实例的正方形;
  3. 在网格线上设置门 (portal);
  4. 使用动态规划 (dynamic programming) 计算最短的k-light环游​;
  5. 将求得的环游​修改为原问题的可行解.

在无特殊前提的情况下, 以下讨论均在\(\mathbb{R}^2\)​中进行.

以下所有对数均以\(2\)​为底.

证明中的记号由于参考资料的不同可能有略微差异.

References

  1. Gutin, G., & Punnen, A.P. (2007). The traveling salesman problem and its variations.
  2. Approximation Algorithms and Hardness of Approximation, EPFL
  3. Geometric Algorithms Seminar, MIT

Implementation

  1. Rodeker, B., Cifuentes, M.V., & Favre, L. (2009). An Empirical Analysis of Approximation Algorithms for Euclidean TSP. CSC.
  2. barbaramartina / C---TSP-Arora-Implementation