Computing the median with uncertainty
Computing the median with uncertainty
复制标题
计算具有不确定性的中位数
DOI：
10.1145/335305.335386
复制
发表时间：
2000
影响因子：
1
通讯作者：
J. Widom
中科院分区：
文献类型：
--
作者：
T. Feder;R. Motwani;R. Panigrahy;Christopher Olston;J. Widom
我们考虑一个新的计算模型与不确定性。期望计算函数f（X1，. . ., Xn），其中X1，. . ., Xn是未知的，但保证位于指定的区间I1，. . ., In.可以以cj为代价查询任何Xj的精确值。我们的目标是以尽可能小的代价将f的值限制在一个精度$\delta$内。我们关注选择函数f，它返回第k个最小参数的值。我们提出了这个问题的最佳离线和在线算法。
We consider a new model for computing with uncertainty. It is desired to compute a function f(X1,. . .,Xn), where X1, . . ., Xn are unknown but guaranteed to lie in specified intervals I1, . . ., In. It is possible to query the precise value of any Xj at a cost cj. The goal is to pin down the value of f to within a precision $\delta$ at a minimum possible cost. We focus on the selection function f which returns the value of the kth smallest argument. We present optimal offline and online algorithms for this problem.