Generalization to d dimensions for d constant also admits a
the problem is APX-complete for any
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 .
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
The maximum geometric traveling salesperson problem (finding the tour of
maximum length) admits a PTAS .
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