Combinatorial Search and Decision Trees

1^st May 2013, 16:00 G12
Prof. Ferdinando Cicalese
Dipartimento di Informatica
Universita' degli Studi di Salerno
Italy

Abstract

In a combinatorial search problem the task is to develop a testing procedure for determining which one of a finite number of possibilities (entities) has occurred (as a result of some event, experiment, decision). Erroneous outcomes of the tests and/or additional probabilistic assumptions on the identity of the entity(ies) to be identified can also be taken into account, as well as cost constraints on the available tests.
Such problems arise in many different contexts and research areas like in medical diagnosis, database theory, networking, laboratory analysis, computer decision making, machine learning, pattern matching and many other fields.

A solution to the above problem is a deterministic algorithm (decision tree) for choosing which tests to perform such that: (i) the unknown entity (information) will always be identified; (ii) as little cost (or resources) as possible will be incurred.

I will discuss several variants of the above problem from different perspectives (e.g., adaptive gap, fault tolerance) trying to show its broad applicability, some of the results I obtained in the area, and future research directions.