Combinatorial Search Algorithms for Function Evaluation

In a typical combinatorial search problem one is required to develop a testing procedure to determine which one of a finite number of possible objects or conditions is present. Such problems arise in medical diagnosis, database theory, networking, laboratory analysis, computer decision making, and many other fields.

More precisely, we define an identification problem as follows:

a) a finite set of objects, O1,..., On, from which an initially unknown object has to be identified;
b) a finite set of m tests (or questions) Q1, ..., Qm, which can be used  to acquire information about the unknown object to be identified;
c) a set of m costs, C1, ..., Cm, where Ci is the cost we incur when we apply test Qi.

In some variants, one also allows erroneous outcomes of the tests and/or makes additional probabilistic assumptions on the identity of the object to be identified.

A solution to the above problem is a deterministic algorithm (decision tree) for choosing which questions to ask such that: (i) the unknown object will always be identified; (ii) as little cost as possible will be incurred.

In this talk, we focus on one particular instance of the above problem: function evaluation with priced information. This problem has applications in automatic diagnosis, strategic decision making, computer games, database query optimization.