English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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.

Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack