Price of Dependence: Stochastic Submodular Maximization with Dependent Items
share
In this paper, we study the stochastic submodular maximization problem with dependent items subject to a variety of packing constraints such as matroid and knapsack constraints. The input of our problem is a finite set of items, and each item is in a particular state from a set of possible states. After picking an item, we are able to observe its state. We assume a monotone and submodular utility function over items and states, and our objective is to select a group of items adaptively so as to maximize the expected utility. Previous studies on stochastic submodular maximization often assume that items' states are independent, however, this assumption may not hold in general. This motivates us to study the stochastic submodular maximization problem with dependent items. We first introduce the concept of degree of independence to capture the degree to which one item's state is dependent on others'. Then we propose a non-adaptive policy based on a modified continuous greedy algorithm and show that its approximation ratio is α(1 - e^-κ/2 + κ/18m^2 - κ + 2/3mκ) where the value of α is depending on the type of constraints, e.g., α=1 for matroid constraint, κ is the degree of independence, e.g., κ=1 for independent items, and m is the number of items.
READ FULL TEXT