Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover

DOI10.1137/1.9781611973402.107zbMath1421.68212arXiv1303.0726OpenAlexW2951161395MaRDI QIDQ5384069

Devorah Kletenik, Amol Deshpande, Lisa Hellerstein

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1303.0726

Mathematics Subject Classification ID

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

Related Items

Totally optimal decision trees for Boolean functions, Decision tree classification with bounded number of errors, Sequential testing in batches, A Polynomial-Time Approximation Scheme for Sequential Batch Testing of Series Systems, Decision trees for function evaluation: simultaneous optimization of worst and expected cost, Unnamed Item, Max-throughput for (conservative) \(k\)-of-\(n\) testing, Evaluation of monotone DNF formulas