University of British Columbia
Computing functions of imprecise inputs using query models
Abstract
dc:descriptionSuppose we want to compute some function (such as convex hull or k-th smallest element), but the input values are imprecise. Can we compute the answer? Perhaps we need some of the input values to be more precise. What is the smallest additional input precision we need for each input to compute the function? We explore a model in which a query to an input allows us to uncover one more "unit" of its precision, at unit cost. Unfortunately, we cannot predict the results of a query in advance. This motivates us to study online algorithms that attempt to minimize the number of queries to compute the function. We compare the cost of online algorithms against the minimum query cost to compute the function. We obtain lower bounds on the ratio of these costs for a variety of simple functions, and create algorithms with matching upper bounds. We also consider a kinetic model in which the results of a query become more imprecise over time (i.e., the inputs move) and our goal is to compute the function of the inputs at some fixed time.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2012
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Suyadi, Simon Aloysius
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/42133