Also called the Minimum Latency Problem.
For fixed-dimensional Euclidean spaces the problem is approximable within
3.59  and admits a quasi polynomial PTAS .
Variation in which the objective is the maximum search ratio, i.e.,
is approximable within 6 and is
Variation in which the graph metric is used (all lengths 1 or )
is approximable within 1.662 .