On computing functions with uncertainty

Abstract

We study the problem of computing a function f(x1,…, xn) given that the actual values of the variables xi's are known only with some uncertainty. For each variable xi, an interval Ii is known such that the value of xi is guaranteed to fall within this interval. Any such interval can be probed to obtain the actual value of the underlying variable; however, there is a cost associated with each such probe. The goal is to adaptively identify a minimum cost sequence of probes such that regardless of the actual values taken by the unprobed xi's, the value of the function f can be computed to within a specified precision.