Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
复制标题
DOI：
10.1145/290179.290180
复制
发表时间：
1998-09-01
影响因子：
2.5
通讯作者：
Arora, S
中科院分区：
文献类型：
--
作者：
Arora, S
我们给出了固定维欧氏TSP的一个多项式时间逼近格式。对于每个固定的c>；1和给定的R-2中的任意n个结点，该方案的一个随机版本在O(Logn)(O(C)时间内找到了最优旅行推销员巡游的(1+1/c)-近似。当节点在R-d中时，运行时间增加到O(n(Logn)((O(根DC))d-1))。对于每一个固定的c，d，运行时间是n poly(Logn)，这在n中几乎是线性的。该算法可以去随机化，但这会使运行时间增加O(Nd)倍。该问题的最佳逼近算法(由Christofides提出)在多项式时间内达到3/2逼近，我们还给出了其他一些NP-Hard欧几里得问题的类似逼近方案：最小Steiner树、R-TSP和k-MST。(k-TSP和k-MST算法的运行时间涉及一个额外的乘法因子k。)以往所有这些问题的最佳逼近算法都实现了恒因子逼近。我们还给出了欧几里得最小代价匹配的有效逼近方案，这是一个可以在多项式时间内精确求解的问题。当使用任何几何范数(如对p大于或等于1的L(P)或其他Minkowski范数)测量距离时，我们的算法几乎不需要修改就可以工作。它们还具有简单的并行(即NC)实现。
We present a polynomial time approximation scheme for Euclidean TSP in fixed dimensions. For every fixed c > 1 and given any n nodes in R-2, a randomized version of the scheme finds a (1 + 1/c)-approximation to the optimum traveling salesman tour in O (log n)(O(c))) time. When the nodes are in R-d, the running time increases to O(n(log n)((O(root dc))d-1)). For every fixed c, d the running time is n poly(log n), that is nearly linear in n. The algorithm can be derandomized, but this increases the running time by a factor O(nd). The previous best approximation algorithm for the problem (due to Christofides) achieves a 3/2-approximation in polynomial time.We also give similar approximation schemes for some other NP-hard Euclidean problems: Minimum Steiner Tree, R-TSP, and k-MST. (The running times of the algorithm for k-TSP and k-MST involve an additional multiplicative factor k.) The previous best approximation algorithms for all these problems achieved a constant-factor approximation. We also give efficient approximation schemes for Euclidean Min-Cost Matching, a problem that can be solved exactly in polynomial time.All our algorithms also work, with almost no modification, when distance is measured using any geometric norm (such as l(p) for p greater than or equal to 1 or other Minkowski norms). They also have simple parallel (i.e., NC) implementations.