Uncertainty Whiteboard Seminar

Adaptive Submodular Ranking

We consider the following stochastic optimization problem. There are n elements and m users. Each user is associated with a monotone submodular function defined on the elements, and is said to be satisfied when the value of this function exceeds 1. We are also given a probability distribution over the users, from which a random user R is drawn. An algorithm needs to select (possibly adaptively) a sequence of elements so as to satisfy the random user R. When an element e is selected, the algorithm receives some feedback which can then be used to refine the probability distribution of R. The objective is to minimize the expected number (or cost) of the selected elements.  We provide a logarithmic factor approximation algorithm for this problem, which is best-possible even in the deterministic setting. As applications we obtain tight results for many previously studied problems (optimal decision tree, decision region determination, deterministic submodular ranking) as well the first results for some new problems (eg. stochastic knapsack-cover with correlations).
This is joint work with Fatemeh Navidi and Prabhanjan Kambadur.