of
m
points in the plane.
.
and
is the discretized Euclidean length
the problem is A
PX
-complete for any
metric [
332
].
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 [
19
].
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 [
1
].
The maximum geometric traveling salesperson problem (finding the tour of
maximum length) admits a nonconstructive PTAS, i.e., the algorithm
does not produce the approximate tour [
38
].
Viggo Kann