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 P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {P}$$\end{document} 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(mnlogmn+nlog2n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(mn\log mn + n\log ^2n)$$\end{document} time. In this paper, we propose a more efficient algorithm solving it in O(mnlogm+nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(mn\log m+n\log n)$$\end{document} time. Besides, we give an algorithm of the same time complexity for the discrete case where each uncertain point follows a discrete distribution.