@techreport{ilprints397,
          number = {1999-41},
            type = {Technical Report},
           title = {Computing the Median With Uncertainty},
          author = {T. Feder and R. Motwani and R. Panigrahy and C. Olston and J. Widom},
       publisher = {Stanford InfoLab},
            year = {1999},
     institution = {Stanford InfoLab},
        keywords = {TRAPP, replication system, bounded replication},
             url = {http://ilpubs.stanford.edu:8090/397/},
        abstract = {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.}
}