Computing the Median with Uncertainty
| Autor: | Tomás Feder, Rajeev Motwani, Christopher Olston, Rina Panigrahy, Jennifer Widom |
|---|---|
| Rok vydání: | 2003 |
| Předmět: | |
| Zdroj: | STOC |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/s0097539701395668 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|