Smallest enclosing ball for probabilistic data
Smallest enclosing ball for probabilistic data
复制标题
概率数据的最小包围球
DOI：
10.1145/2582112.2582114
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Dan Feldman
中科院分区：
文献类型：
--
作者：
Alexander Munteanu;C. Sohler;Dan Feldman
本文讨论了在概率数据条件下计算一组点的最小封闭球的问题。在我们的设置中，n个点中的任何一个都可能不是或可能出现在有限多个位置中的一个，遵循其自己的离散概率分布。因此，目标被认为是一个随机变量，我们的目标是找到一个中心，根据它们的分布最小化到这些点的期望最大距离。我们在本文中提出的主要贡献是第一个多项式时间（1 + λ）逼近算法，用于扩展到流设置的概率最小封闭球问题。
This paper deals with computing the smallest enclosing ball of a set of points subject to probabilistic data. In our setting, any of the n points may not or may occur at one of finitely many locations, following its own discrete probability distribution. The objective is therefore considered to be a random variable and we aim at finding a center minimizing the expected maximum distance to the points according to their distributions. Our main contribution presented in this paper is the first polynomial time (1 + ϵ)-approximation algorithm for the probabilistic smallest enclosing ball problem with extensions to the streaming setting.
影响因子：
1.3
作者：
Ackermann, Marcel R.;Bloemer, Johannes;Sohler, Christian
通讯作者：
Sohler, Christian