We present a randomized polynomial time approximation scheme forEuclidean TSP in R2 that is substantially more efficient thanour earlier scheme (1996) (and the scheme of Mitchell (1996)). For anyfixed c>1 and any set of n nodes in the plane, the new scheme finds a(1+1/c)-approximation to the optimum traveling salesman tour inO(n(logn)O(c)) time. (Our earlier scheme ran in nO(C) time.) For points in Rd the algorithm runs inO(n(logn)(O(√dc)d-1)) time. This time is polynomial(actually nearly linear) for every fixed c, d. Designing such apolynomial-time algorithm was an open problem (our earlier algorithm(1996) ran in superpolynomial time for d⩾3). The algorithmgeneralizes to the same set of Euclidean problems handled by theprevious algorithm, including Steiner Tree, κ-TSP, κ-MST,etc, although for κ-TSP and κ-MST the running time getsmultiplied by κ. We also use our ideas to design nearly-lineartime approximation schemes for Euclidean versions of problems that areknown to be in P, such as Minimum Spanning Tree and Min Cost PerfectMatching. All our algorithms can be derandomized, though the runningtime then increases by O(nd) in Rd. They also havesimple parallel implementations (say, in NC2)
展开▼
