MINIMUM GEOMETRIC TRAVELING SALESPERSON

• INSTANCE: Set $C\subseteq Z\times Z$ of m points in the plane.
• SOLUTION: A tour of C, i.e., a permutation $\pi: [1..m]\rightarrow[1..m]$.
• MEASURE: The length of the tour, where the distance between $(x_1,y_1)$ and $(x_2,y_2)$ is the discretized Euclidean length
  
  $$\left\lceil\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\right\rceil.$$
  
  

  
  

• Good News: Admits a PTAS [33].

• Comment: Generalization to d dimensions for d constant also admits a PTAS [34]. In $R^m$ the problem is APX-complete for any $l_p$ metric [452]. The variation in which an integer $k \leq m$ is given in the input and only at least k of the cities must be included in the tour also admits a PTAS [33]. Minimum geometric angular TSP, the variation in which the sum of the direction changes in the tour is minimized, is approximable within $O(\log m)$. The same bound is valid also when there may be several tours covering all the cities [4]. The maximum geometric traveling salesperson problem (finding the tour of maximum length) admits a PTAS [65].

  Variation in which the input is given as k possibly overlapping simple polygons in the plane, and where the objective is to find the shortest tour that visits (intersects) each polygon, is approximable within $O(\log k)$ [374].

• Garey and Johnson: ND23