Constrained Stochastic Submodular Maximization with State-Dependent
  Costs
  In this paper, we study the constrained stochastic submodular maximization
problem with state-dependent costs. The input of our problem is a set of items
whose states (i.e., the marginal contribution and the cost of an item) are
drawn from a known probability distribution. The only way to know the realized
state of an item is to select that item. We consider two constraints, i.e.,
\emph{inner} and \emph{outer} constraints. Recall that each item has a
state-dependent cost, and the inner constraint states that the total
\emph{realized} cost of all selected items must not exceed a give budget. Thus,
inner constraint is state-dependent. The outer constraint, one the other hand,
is state-independent. It can be represented as a downward-closed family of sets
of selected items regardless of their states. Our objective is to maximize the
objective function subject to both inner and outer constraints. Under the
assumption that larger cost indicates larger "utility", we present a constant
approximate solution to this problem.
