INSTANCE:
Graph
,
start vertex ,
length
for each
satisfying
the triangle inequality.
SOLUTION:
A walk starting in r visiting all vertices in G, i.e.,
a permutation
such that
,
where
describes in which order the vertices are
visited for the first time.
MEASURE:
,
where
is the
total distance traversed in the walk from r until we first visit
v.
Comment:
Also called the Minimum Latency Problem.
For fixed-dimensional Euclidean spaces the problem is approximable within
3.59 [195] and admits a quasi polynomial PTAS [38].
Variation in which the objective is the maximum search ratio, i.e.,
is approximable within 6 and is
APX-complete [339].
Variation in which the graph metric is used (all lengths 1 or )
is approximable within 1.662 [339].