Paper Info
Title
Adaptive Cascade Submodular Maximization
Abstract
In this paper, we propose and study the cascade submodular maximization problem under the adaptive setting. The input of our problem is a set of items, each item is in a particular state (i.e., the marginal contribution of an item) which is drawn from a known probability distribution. However, we can not know its actual state before selecting it. As compared with existing studies on stochastic submodular maximization, one unique setting of our problem is that each item is associated with a continuation probability which represents the probability that one can continue to select the next item after selecting the current one. Intuitively, this term captures the externality of one item to all its subsequent items in terms of the opportunity of being selected. Therefore, the actual set of items that can be selected by a policy depends on the specific ordering it adopts to select items, this makes our problem fundamentally different from classical submodular set optimization problems. Our objective is to identify the best sequence of selecting items so as to maximize the expected utility of the selected items. We propose a class of stochastic utility functions, \emph{adaptive cascade submodular functions}, and show that the objective functions in many practical application domains satisfy adaptive cascade submodularity. Then we develop a $\frac{1-1/e}{8}$ approximation algorithm to the adaptive cascade submodular maximization problem.
Year
DOI
Venue
2021
10.5555/3463952.3464102
AAMAS
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Tang Shaojie12224157.73
Jing Yuan223711.92