## Computing the Median with Uncertainty

### Tomas Feder, Rajeev Motwani, Rina Panigrahy, Chris Olston, Jennifer Widom

#### Abstract

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 *k*th smallest argument. We present optimal offline and online algorithms for this problem.
### Conference Paper (STOC 2000): [PS], [PDF]. Citation: [BibTeX]

### Journal Paper (SIAM Journal on Computing): [PDF].

### TRAPP Project Web Page: [HTML]