Algorithms and Adaptivity Gaps for Stochastic Probing

A stochastic probing problem consists of a set of elements whose values are independent random variables. The algo-rithm knows the distributions of these variables, but not the actual outcomes. The only way to learn the actual out-comes is to probe these elements. However, there are con-straints on which set of elements may be probed. (E.g., we may have to travel in some metric to probe elements but have limited time.) These constraints are called outer constraints. We want to develop an algorithm that picks some set of elements to maximize the (expected) value, sub-ject to the picked subset of elements satisfying some other set of constraints, called the inner constraints. In the past, probing problems were studied for the case when both inner and outer constraints were intersections of matroids; these modeled kidney matching and Bayesian auctions applica-tions. One limitation of past work was their reliance on linear-programming-like techniques, which made going be-yond matroid-like structures difficult. In this work, we give a very general adaptivity gap re-sult that holds for all prefix-closed outer constraints, as long as the inner constraints are intersections of matroids. The adaptivity gap is O(logn) for any constant number of inner matroid constraints. The prefix-closedness captures most “reasonable ” outer constraints, like orienteering, connectiv-ity, and precedence. Based on this we obtain the first ap-proximation algorithms for a number of stochastic probing problems, which have applications, e.g., to path-planning and precedence-constrained scheduling.