satisfying the
triangle inequality.
.
if the distance function is asymmetric
[
115
].
Variation in which the distances are only 1 or 2 is still A
PX
-complete,
but approximable within 7/6 [
285
] if the distance function is
symmetric and 17/12 if it is asymmetric [
338
].
In the special case in which the distances are the shortest path lengths in a
given unweighted maximal planar graph, a solution can be found whose length
is at most
3/2(|V|-3)
[
277
].
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 [
16
].
Another generalization in which the salesperson has to rearrange some objects
while following the route is approximable within 2.5 [
12
].
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
2-1/(|V|-1)
[
134
].
A clustered generalization in which vertices are partitioned into clusters that
must be traversed consecutively is approximable within 7/2
[
17
].
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 A
PX
-complete [
54
].
A combination of this problem and the matching problem, also called
Printed Circuit Board Assembly
, is approximable within 2.5
[
271
].
Viggo Kann