Variation in which the triangle inequality is relaxed to
for
is approximable within
[23].
The generalization in which, for each city, a neighborhood is specified in
which the salesperson can meet the client, is also approximable for a
variety of neighborhood types such as unit segments, unit circles, and unit
rectangles [29].
Another generalization in which the salesperson has to rearrange some objects
while following the route is approximable within 2.5 [25].
A prize-collecting variation in which a penalty is associated with each vertex
and the goal is to minimize the cost of the tour and the vertices not in
the tour is approximable within
[197].
A clustered generalization in which vertices are partitioned into
clusters that must be traversed consecutively is approximable within
2.75 in the general case, within 2.643 if the starting
vertex in each cluster is given, within 1.9091 if the starting and
ending vertices of each cluster are specified, within 1.8
if in each cluster two vertices are given and we are
free to choose any one as starting vertex and the other as ending
vertex [215].
A variation in which vertices can be revisited and the goal is to minimize the
sum of the latencies of all vertices, where the latency of a vertex c is the
length of the tour from the starting point to c, is approximable within 29
and is APX-complete [83].
A combination of this problem and the matching problem, also called
Printed Circuit Board Assembly, is approximable within 2.5
[375].
Finally, the variation in which a Hamiltonian path is looked for rather than a
tour is also approximable within 1.5 in the general case
while if both end vertices are specified it is
approximable within 5/3 [259].