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 kth smallest argument. We present optimal offline and online algorithms for this problem.

Computing the Median with Uncertainty

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

Abstract

Conference Paper (STOC 2000): [PS], [PDF]. Citation: [BibTeX]

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

TRAPP Project Web Page: [HTML]