Next:
ND30 MINIMUM METRIC
Up:
Routing Problems
Previous:
Routing Problems
-
I
NSTANCE
:
Set
C
of
m
cities, distances
for each pair of cities
.
-
S
OLUTION
:
A tour of
C
, i.e., a permutation
.
-
M
EASURE
:
The length of the tour, i.e.,
.
-
Bad News:
NPO-complete [
280
].
-
Comment:
The corresponding maximization problem (finding the tour of maximum length)
is approximable within 7/5 if the distance function is symmetric and
63/38 if it is asymmetric [
245
].
-
Garey and Johnson:
ND22
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997