Suppose we are given a submodular function @math over a set of elements, and we want to maximize its value subject to certain constraints. Good approximation algorithms are known for such problems under both monotone and non-monotone submodular functions. We consider these problems in a stochastic setting, where elements are not all active and we can only get value from active elements. Each element @math is active independently with some known probability @math , but we don't know the element's status . We find it out only when we the element @math ---probing reveals whether it's active or not, whereafter we can use this information to decide which other elements to probe. Eventually, if we have a probed set @math and a subset @math of active elements in @math , we can pick any @math and get value @math . Moreover, the sequence of elements we probe must satisfy a given ---e.g., these may be given by a matroid, or an orienteering constraint, or deadline, or precedence constraint, or an arbitrary downward-closed constraint---if we can probe some sequence of elements we can probe any prefix of it. What is a good strategy to probe elements to maximize the expected value? In this paper we study the gap between adaptive and non-adaptive strategies for @math being a submodular or a fractionally subadditive (XOS) function. If this gap is small, we can focus on finding good non-adaptive strategies instead, which are easier to find as well as to represent. We show that the adaptivity gap is a constant for monotone and non-monotone submodular functions, and logarithmic for XOS functions of small . These bounds are nearly tight. Our techniques show new ways of arguing about the optimal adaptive decision tree for stochastic problems.
@cite_2: A stochastic probing problem consists of a set of elements whose values are independent random variables. The algorithm knows the distributions of these variables, but not the actual outcomes. The only way to learn the actual outcomes is to probe these elements. However, there are constraints 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, subject 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 applications. One limitation of past work was their reliance on linear-programming-like techniques, which made going beyond matroid-like structures difficult. In this work, we give a very general adaptivity gap result that holds for all prefix-closed outer constraints, as long as the inner constraints are intersections of matroids. The adaptivity gap is O(log n) for any constant number of inner matroid constraints. The prefix-closedness captures most "reasonable" outer constraints, like orienteering, connectivity, and precedence. Based on this we obtain the first approximation algorithms for a number of stochastic probing problems, which have applications, e.g., to path-planning and precedence-constrained scheduling.
The previous work of the authors @cite_2 gave results for the case where @math was the rank function of matroids (or their intersections). That work bounded the adaptivity gap by logarithmic factors, and gave better results for special cases like uniform and partition matroids. This work both improves the quantitative bounds (down to small constants), generalizes it to all submodular functions with the hope of getting to all subadditive functions, and arguably also makes the proof simpler.