ICS Theory Group

ICS 269, Fall 1996: Theory Seminar

25 Oct 1996:
Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems
Joseph Wang, ICS, UC Irvine

Arora presents a polynomial time approximation scheme for Euclidean TSP in R2 that finds a (1+epsilon)-approximation tour in time nO(1/epsilon). The scheme can be extended to higher dimensions and other Euclidean problems in which the objective function is a sum of edge lengths.

(From a FOCS '96 paper by Sanjeev Arora)