Feder, T. and Motwani, R. and Panigrahy, R. and Olston, C. and Widom, J. (2002) Computing the Median with Uncertainty. Technical Report. Stanford InfoLab. (Publication Note: SIAM Journal on Computing)
| BibTeX | DublinCore | EndNote | HTML |
This is the latest version of this item.
![[img]](/style/images/fileicons/application_pdf.png)
| PDF 209Kb |
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.
| Item Type: | Techreport (Technical Report) | |
|---|---|---|
| Subjects: | Computer Science > Distributed Systems | |
| Projects: | TRAPP | |
| Related URLs: | Project Homepage | http://infolab.stanford.edu/trapp/ |
| ID Code: | 743 | |
| Deposited By: | Import Account | |
| Deposited On: | 24 Oct 2002 17:00 | |
| Last Modified: | 25 Dec 2008 09:12 |
Available Versions of this Item
- Computing the Median With Uncertainty. (deposited 25 Feb 2000 16:00)
- Computing the Median with Uncertainty. (deposited 24 Oct 2002 17:00) [Currently Displayed]
Download statistics
Repository Staff Only: item control page
