Next:
ND33 MINIMUM METRIC
Up:
Routing Problems
Previous:
ND31 MINIMUM GEOMETRIC
-
I
NSTANCE
:
Set
C
of
m
cities, an initial city
, distances
satisfying the triangle inequality.
-
S
OLUTION
:
A collection of
k
subtours, each containing the initial city
, such that
each city is in at least one subtour.
-
M
EASURE
:
The maximum length of the
k
subtours.
-
Good News:
Approximable within
1-1/k
plus the performance ratio of the M
INIMUM
M
ETRIC
T
RAVELING
S
ALESPERSON
P
ROBLEM
,
i.e., within
[
112
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997