Decision Making under Uncertainty

Almost all (important) decision problems are inevitably subject to some level of uncertainty either about data measurements, the parameters, or predictions describing future evolution. The significance of handling uncertainty is further amplified by the large volume of uncertain data automatically generated by modern data gathering or integration systems. Examples include imprecise sensor measurements in a sensor network, inconsistent information collected from different sources in a data integration application, noisy observation data in scientific domains, and so on. Various types of problems of decision making under uncertainty have been a subject of extensive research in computer science, economics and social science. In this talk, I will focus on two important problems in this domain. The first problem concerns with ranking and top-k query processing over probabilistic databases. We propose the notion of “parameterized ranking functions” (PRF), that generalize or can approximate many of the previously proposed ranking functions and present novel exact or approximate algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations or the probability distributions are continuous. The second problem deals with the stochastic versions of a more general class of combinatorial problems. We argue that the expected value is inadequate in capturing different types of risk-averse or risk-prone behaviors. Therefore, we consider a more general objective which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (which becomes a special case).
Our result generalizes several prior works on stochastic shortest path and stochastic knapsack.
If time allows, I will also briefly discuss some of my other research works, such as stochastic matching, distributed multi-query processing.