The two-center problem of uncertain points on a real line

Facility location problems on uncertain demand data have attracted significant attention recently. In this paper, we consider the two-center problem on uncertain points on a real line. The input is a set $$\mathcal {P}$$ P of n uncertain points on the line. Each uncertain point is represented by a probability density function that is a piecewise uniform distribution (i.e., a histogram) of complexity m. The goal is to find two points (centers) on the line so that the maximum expected distance of all uncertain points to their expected closest centers is minimized. A previous algorithm for the uncertain k-center problem can solve this problem in $$O(mn\log mn + n\log ^2n)$$ O ( m n log m n + n log 2 n ) time. In this paper, we propose a more efficient algorithm solving it in $$O(mn\log m+n\log n)$$ O ( m n log m + n log n ) time. Besides, we give an algorithm of the same time complexity for the discrete case where each uncertain point follows a discrete distribution.