The Two-Center Problem of Uncertain Points on Trees

In this paper, we consider the (weighted) two-center problem of uncertain points on a tree. Given are a tree T and a set \(\mathcal {P}\) of n (weighted) uncertain points each of which has m possible locations on T associated with probabilities. The goal is to compute two points on T, i.e., two centers with respect to \(\mathcal {P}\) , so that the maximum (weighted) expected distance of n uncertain points to their own expected closest center is minimized. This problem can be solved in \(O(|T|+ n^{2}\log n\log mn + mn\log ^2 mn \log n)\) time by the algorithm for the general k-center problem. In this paper, we give a more efficient and simple algorithm that solves this problem in \(O(|T| + mn\log mn)\) time.