The weighted $k$-center problem in graphs is a classical facility location problem where we place $k$ centers on the graph, which minimize the maximum weighted distance of a vertex to its nearest center. We study this problem when the underlying graph is a cactus with $n$ vertices and present an $O(n \log^2 n)$ time algorithm for the same. This time complexity improves upon the $O(n^2)$ time algorithm by Ben-Moshe et al. [TCS 2007], which is the current state-of-the-art.

翻译：基于仙人掌图的带权$k$-中心问题的次二次时间算法 翻译后的摘要： 我们研究了该问题的仙人掌图情形，即在仙人掌图上放置 $k$ 个中心，目标是使每个顶点到其最近中心的带权距离最小。我们提出了一种复杂度为 $O(n\log^2 n)$ 的算法，该算法优于 Ben-Moshe 等人的 $O(n^2)$ 时间算法，后者是当前的最优算法。