[ Pagewise preview ]
| Category | Value | ||
| Available via | http://dbpubs.stanford.edu/pub/2002-50 | ||
| Previous version | 1999-41 | ||
| Submitted on | 25th of October 2002 | ||
| Author | Feder, T.; Motwani, R.; Panigrahy, R.; Olston, C.; Widom, J. | ||
| Title | Computing the Median with Uncertainty | ||
| Date of publication | 2002 | ||
| Published in | SIAM Journal on Computing | ||
| Citation | Feder, T.; Motwani, R.; Panigrahy, R.; Olston, C.; Widom, J.. Computing the Median with Uncertainty, SIAM Journal on Computing | ||
| Number of pages | 12 | ||
| Language | English | ||
| Project | TRAPP | ||
| Type | Conference or Journal Paper | ||
| Subject group | Distributed Systems | ||
| 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. | ||
| Sponsored by | National Science Foundation | ||
| Fulltext source |
| Management of the document by | siroker@db.stanford.edu
| |
[ Pagewise preview ]