%0 Report
%9 Technical Report
%A Feder, T.
%A Motwani, R.
%A Panigrahy, R.
%A Olston, C.
%A Widom, J.
%D 1999
%F ilprints:397
%I Stanford InfoLab
%K TRAPP, replication system, bounded replication
%T Computing the Median With Uncertainty
%U http://ilpubs.stanford.edu:8090/397/
%X We consider a new model for computing with uncertainty.  It is desired to compute a function f(X_1,...,X_n) where X_1,...,X_n are unknown, but guaranteed to lie in specified intervals I_1,...,I_n. It is possible to query the precise value of any X_j at a cost c_j. The goal is to pin down the value of f to within a precision p 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.