The Two-Center Problem of Uncertain Points on Trees

Abstract

In this paper, we consider the (weighted) two-center problem of uncertain points on a tree. Given are a tree $T$ and a set $\calP$ 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 $\calP$, 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.

A preliminary version of this paper appeared in Proceedings of the 16th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2023)