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

DOI10.1145/2876506zbMath1421.68211OpenAlexW2342745562MaRDI QIDQ4962618

Devorah Kletenik, Amol Deshpande, Lisa Hellerstein

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2876506

zbMATH Keywords

sequential testingBoolean function evaluation

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Non-adaptive stochastic score classification and explainable halfspace evaluation, Sequential testing in batches, A General Framework for Approximating Min Sum Ordering Problems, Adaptivity gaps for the stochastic Boolean function evaluation problem, Submodular goal value of Boolean functions, Unnamed Item, Scenario Submodular Cover, Adaptive Submodular Ranking and Routing, Robust budget allocation via continuous submodular functions, Unnamed Item, The stochastic Boolean function evaluation problem for symmetric Boolean functions, Unnamed Item, Algorithms for the unit-cost stochastic score classification problem, A Tight Bound for Stochastic Submodular Cover