Speaker: Viswanath Nagarjan (IBM TJ Watson)
Title: A Stochastic Probing Problem with Applications

Abstract:
We study a general stochastic probing problem defined on a 
ground-set V, where each element e in V is ``active'' 
independently with probability p(e). Elements have weights 
w(e) and the goal is to maximize the weight of a chosen 
subset S of active elements. However, an algorithm only knows 
the p(e) values up front-- to determine whether or not an 
element e is active, it must probe e. If element e is probed 
and happens to be active, then e must irrevocably be added 
to the chosen set S; if e is not active then it is not 
included in S. Moreover, two constraints must be met under 
every outcome: (1) the set Q of probed elements satisfy an 
``outer'' packing constraint, and (2) the set S of chosen 
elements satisfy an ``inner'' packing constraint. The kinds 
of packing constraints we consider are intersections of 
matroids and knapsacks. Our results provide a simple and 
unified view of results in stochastic matching and Bayesian 
mechanism design, and can also handle more general constraints 
in these contexts. 

This is joint work with Anupam Gupta.