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.