The Two-Center Problem of Uncertain Points on a Real Line
Document Type
Article
Publication Date
3-2023
Publication Title
Journal of Combinatorial Optimization
Abstract
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.
Repository Citation
Xu, Haitao and Zhang, Jingru, "The Two-Center Problem of Uncertain Points on a Real Line" (2023). Electrical and Computer Engineering Faculty Publications. 505.
https://engagedscholarship.csuohio.edu/enece_facpub/505
DOI
10.1007/s10878-023-00996-w
Volume
45
Issue
2
