  A searcher faces a graph with edge lengths and vertex weights, initially
having explored only a given starting vertex. In each step, the searcher adds
an edge to the solution that connects an unexplored vertex to an explored
vertex. This requires an amount of time equal to the edge length. The goal is
to minimize the weighted sum of the exploration times over all vertices. We
show that this problem is hard to approximate and provide algorithms with
improved approximation guarantees. For the general case, we give a
$(2\mathrm{e}+\varepsilon)$-approximation for any $\varepsilon > 0$. For the
case that all vertices have unit weight, we provide a
$2\mathrm{e}$-approximation. Finally, we provide a PTAS for the case of a
Euclidean graph. Previously, for all cases only an $8$-approximation was known.
