Next: MINIMUM METRIC TRAVELING K-SALESPERSON Up: Routing Problems Previous: MINIMUM METRIC TRAVELING SALESPERSON Index

### MINIMUM GEOMETRIC TRAVELING SALESPERSON

- INSTANCE: Set of m points in the plane.
- SOLUTION: A tour of C, i.e., a permutation .
- MEASURE: The length of the tour, where the distance between (x1,y1) and (x2,y2) is the discretized Euclidean length

- Good News: Admits a PTAS [31].

- Comment: Generalization to d dimensions for d constant also admits a PTAS [32]. In Rm the problem is APX-complete for any lp metric [429]. The variation in which an integer is given in the input and only at least k of the cities must be included in the tour also admits a PTAS [31]. Minimum geometric angular TSP, the variation in which the sum of the direction changes in the tour is minimized, is approximable within . 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 [61].

  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 [354].

- Garey and Johnson: ND23

Next: MINIMUM METRIC TRAVELING K-SALESPERSON Up: Routing Problems Previous: MINIMUM METRIC TRAVELING SALESPERSON Index