图上不确定点的k中心问题 (The k-Center Problem of Uncertain Points on Graphs)

In this paper, we study the $k$-center problem of uncertain points on a graph. Given are an undirected graph $G = (V, E)$ and a set $\mathcal{P}$ of $n$ uncertain points where each uncertain point with a non-negative weight has $m$ possible locations on $G$ each associated with a probability. The problem aims to find $k$ centers (points) on $G$ so as to minimize the maximum weighted expected distance of uncertain points to their expected closest centers. No previous work exist for the $k$-center problem of uncertain points on undirected graphs. We propose exact algorithms that solve respectively the case of $k=2$ in $O(|E|^2m^2n\log |E|mn\log mn )$ time and the problem with $k\geq 3$ in $O(\min\{|E|^km^kn^{k+1}k\log |E|mn\log m, |E|^kn^\frac{k}{2}m^\frac{k^2}{2}\log |E|mn\})$ time, provided with the distance matrix of $G$. In addition, an $O(|E|mn\log mn)$-time algorithmic approach is given for the one-center case.

翻译：本文研究图上的不确定点k中心问题。给定一个无向图$G = (V, E)$和一个包含$n$个不确定点的集合$\mathcal{P}$，其中每个带非负权重的不确定点在$G$上具有$m$个可能位置，每个位置对应一个概率。该问题的目标是找到图上的$k$个中心点，以最小化不确定点到其期望最近中心的加权最大期望距离。目前尚无针对无向图上不确定点k中心问题的现有研究。我们提出了精确算法：对于$k=2$的情况，算法时间复杂度为$O(|E|^2m^2n\log |E|mn\log mn)$；对于$k\geq 3$的情况，在已知图$G$距离矩阵的前提下，算法时间复杂度为$O(\min\{|E|^km^kn^{k+1}k\log |E|mn\log m, |E|^kn^\frac{k}{2}m^\frac{k^2}{2}\log |E|mn\})$。此外，针对单中心情况，我们给出了一个时间复杂度为$O(|E|mn\log mn)$的算法框架。