Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
复制标题
DOI：
10.1145/2876506
复制
发表时间：
2016-06-01
影响因子：
1.3
通讯作者：
Kletenik, Devorah
中科院分区：
文献类型：
--
作者：
Deshpande, Amol;Hellerstein, Lisa;Kletenik, Devorah
针对随机子模集覆盖(SSSC)问题，提出了一种新的近似算法--自适应对偶贪婪算法。利用该算法得到了一个求解线性门限公式的随机布尔函数求值问题(SBFE)的3-近似算法。我们还得到了相关随机最小背包问题的3-近似算法和2-近似算法，证明了SSSC问题的一个新的逼近界，即Golovin和Krase的自适应贪婪算法。我们还考虑了一种用自适应贪婪算法逼近SBFE问题的方法，我们称之为Q值方法。这种方法对于合取/析取范式公式的求值很容易得到一个新的结果，并将其应用于同时求值问题和一个排序问题。然而，我们证明了Q值方法不能用于获得LTFS或一次读取析取范式公式的SBFE问题的次线性逼近因子。
We present a new approximation algorithm for the stochastic submodular set cover (SSSC) problem called adaptive dual greedy. We use this algorithm to obtain a 3-approximation algorithm solving the stochastic Boolean function evaluation (SBFE) problem for linear threshold formulas (LTFs). We also obtain a 3-approximation algorithm for the closely related stochastic min-knapsack problem and a 2-approximation for a variant of that problem.We prove a new approximation bound for a previous algorithm for the SSSC problem, the adaptive greedy algorithm of Golovin and Krause.We also consider an approach to approximating SBFE problems using the adaptive greedy algorithm, which we call the Q-value approach. This approach easily yields a new result for evaluation of CDNF (conjunctive / disjunctive normal form) formulas, and we apply variants of it to simultaneous evaluation problems and a ranking problem. However, we show that the Q-value approach provably cannot be used to obtain a sublinear approximation factor for the SBFE problem for LTFs or read-once disjunctive normal form formulas.