The Two-Center Problem of Uncertain Points on a Real Line
Journal of Combinatorial Optimization
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 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(2) n) time. In this paper, we propose a more efficient algorithm solving it in O(mn 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.
Xu, Haitao and Zhang, Jingru, "The Two-Center Problem of Uncertain Points on a Real Line" (2023). Electrical Engineering & Computer Science Faculty Publications. 505.