论文标题
自适应级联级别的最大化
Adaptive Cascade Submodular Maximization
论文作者
论文摘要
在本文中，我们提出并研究了自适应环境下的级联下管最大化问题。我们问题的输入是一组项目，每个项目都处于特定状态（即项目的边际贡献），该状态是从已知概率分布中得出的。但是，我们在选择它之前不知道其实际状态。与现有的关于随机次传导最大化的研究相比，我们问题的一个独特设置是，每个项目都与持续概率相关联，该概率表示允许人们在选择当前项目后继续选择下一个项目的概率。从直觉上讲，该术语捕获了根据被选中的机会选择一项为所有后续项目选择一项的外部性。因此，策略可以选择的实际项目集取决于其为选择项目所采用的特定顺序，这使我们的问题从根本上与经典的subsodular集合优化问题不同。我们的目标是确定选择项目的最佳顺序，以最大程度地提高所选项目的预期效用。我们提出了一类随机效用函数，\ emph {自适应级联反式函数}，并表明许多实际应用域中的目标函数满足自适应级联反向性。然后，我们将$ 0.12 $的近似算法开发到自适应级联反化最大化问题。
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 is allowed to continue to select the next item after selecting the current one. Intuitively, this term captures the externality of selecting 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 $0.12$ approximation algorithm to the adaptive cascade submodular maximization problem.
