One-dimensional k-center on uncertain data
One-dimensional k-center on uncertain data
复制标题
不确定数据上的一维 k 中心
DOI：
10.1016/j.tcs.2015.08.017
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Jingru Zhang
中科院分区：
文献类型：
--
作者：
Haitao Wang;Jingru Zhang
由于许多测量数据的不精确性，不确定性数据问题引起了人们的广泛关注。本文研究了一维不确定数据的k-中心问题。输入是一组P（加权）不确定点的真实的线，每个不确定点是由其概率密度函数（pdf），这是一个分段均匀的函数（即直方图）指定。目标是找到直线上的k个点的集合Q，以最小化从P的不确定点到Q中期望的最近点的最大期望距离。我们提出了有效的算法，这个不确定的k-中心问题和他们的运行时间几乎匹配的“确定性”的k-中心问题。
Problems on uncertain data have attracted significant attention due to the imprecise nature of many measurement data. In this paper, we consider the k-center problem on one-dimensional uncertain data. The input is a set P of (weighted) uncertain points on a real line, and each uncertain point is specified by its probability density function (pdf) which is a piecewise-uniform function (ie, a histogram). The goal is to find a set Q of k points on the line to minimize the maximum expected distance from the uncertain points of P to their expected closest points in Q. We present efficient algorithms for this uncertain k-center problem and their running times almost match those for the “deterministic” k-center problem.