Scenario Submodular Cover
Scenario Submodular Cover
复制标题
场景子模块覆盖
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
P. Lin
中科院分区：
文献类型：
--
作者：
Nathaniel Grammel;L. Hellerstein;Devorah Kletenik;P. Lin
我们引入场景子模覆盖问题。在这个问题中，目标是相对于经验联合概率分布（由实现的加权样本作为输入给出）产生具有最小预期成本的覆盖。该问题与 Golovin 和 Krause [6] 研究的随机子模覆盖问题相对应，该问题假设自变量。我们给出了场景子模覆盖的两种近似算法。假设整数值效用函数和整数权重，第一个实现的近似因子为 (O(log Qm))，其中 m 是样本大小，Q 是目标效用。第二种更简单的算法实现了 (O(log QW)) 的近似因子，其中 W 是权重之和。我们通过建立以前的相关工作（在[4,6,15]中）并利用我们称为场景或修改的技术来实现我们的界限。我们将这些算法应用于一个新问题：场景布尔函数求值。我们的结果适用于涉及由其支持明确指定的分布的其他问题。
We introduce the Scenario Submodular Cover problem. In this problem, the goal is to produce a cover with minimum expected cost, with respect to an empirical joint probability distribution, given as input by a weighted sample of realizations. The problem is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause [6], which assumes independent variables. We give two approximation algorithms for Scenario Submodular Cover. Assuming an integer-valued utility function and integer weights, the first achieves an approximation factor of (O(log Qm)), where m is the sample size and Q is the goal utility. The second, simpler algorithm achieves an approximation factor of (O(log QW)), where W is the sum of the weights. We achieve our bounds by building on previous related work (in [4, 6, 15]) and by exploiting a technique we call the Scenario-OR modification. We apply these algorithms to a new problem, Scenario Boolean Function Evaluation. Our results have applciations to other problems involving distributions that are explicitly specified by their support.