Computing the Median with Uncertainty
Tomás Feder, Rajeev Motwani, Rina Panigrahy, Chris Olston, Jennifer Widom · SIAM Journal on Computing · 2003
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 $\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.