Feder, T. and Motwani, R. and Panigrahy, R. and Olston, C. and Widom, J. (1999) *Computing the Median With Uncertainty.* Technical Report. Stanford InfoLab. (Publication Note: 32nd ACM Symposium on Theory of Computing (STOC 2000), Portland, Oregon, May 2000)

BibTeX | DublinCore | EndNote | HTML |

There is a more recent version of this item available. |

| PDF 211Kb |

## Abstract

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 p 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) | |
---|---|---|

Uncontrolled Keywords: | TRAPP, replication system, bounded replication | |

Subjects: | Computer Science > Data Mining | |

Projects: | MIDAS TRAPP | |

Related URLs: | Project Homepage, Project Homepage | http://infolab.stanford.edu/midas/midas.html, http://infolab.stanford.edu/trapp/ |

ID Code: | 397 | |

Deposited By: | Import Account | |

Deposited On: | 25 Feb 2000 16:00 | |

Last Modified: | 28 Dec 2008 08:59 |

### Available Versions of this Item

- Computing the Median With Uncertainty. (deposited 25 Feb 2000 16:00)
**[Currently Displayed]**

## Download statistics

Repository Staff Only: item control page