- 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*.

*Good News:*Approximable within 10.78 [184].*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].