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 vertex-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 case that all vertices have unit weight, we provide a $2e$-approximation. For the general case, we give a $(5e/2+\varepsilon)$-approximation for any $\varepsilon > 0$. Previously, for both cases only an $8$-approximation was known. Finally, we provide a PTAS for the case of a Euclidean graph.

翻译：搜索者面对的是一个带有边缘长度和顶点重量的图形, 最初只探索了一个特定的起始顶点。 在每步中, 搜索者都会在将未探索的顶点连接到所探索的顶点的解决方案中添加一个边缘。 这需要与边缘长度相等的时间。 目标是将所有顶点的勘探时间的顶点加权总和最小化。 我们显示, 这个问题很难估计, 并且提供精确度保证的算法。 对于所有顶点都有单位重量的情况, 我们提供$$2的近似值。 对于一般情况, 我们给任何 $\varepsilon > 0 美元 。 之前, 对于这两个情况, 我们只知道$8 $- aglocimation 。 最后, 我们为 Euclidean 图提供 PTAS 。