Stanford InfoLab Publication Server

Computing the Median with Uncertainty

Feder, T. and Motwani, R. and Panigrahy, R. and Olston, C. and Widom, J. (2002) Computing the Median with Uncertainty. Technical Report. Stanford InfoLab. (Publication Note: SIAM Journal on Computing)


This is the latest version of this item.



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.

Item Type:Techreport (Technical Report)
Subjects:Computer Science > Distributed Systems
Related URLs:Project Homepage
ID Code:743
Deposited By:Import Account
Deposited On:24 Oct 2002 17:00
Last Modified:25 Dec 2008 09:12

Available Versions of this Item

Download statistics

Repository Staff Only: item control page