- 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
and
is the discretized Euclidean length

*Good News:*Admits a PTAS [33].*Comment:*Generalization to*d*dimensions for*d*constant also admits a PTAS [34]. In the problem is APX-complete for any metric [452]. 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 [33]. 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 [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 [374].*Garey and Johnson:*ND23