Open Collections

Computing functions of imprecise inputs using query models

University of British Columbia

Suppose 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.

Text

2012-04-20

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/42133

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/