Adaptivity gaps for the stochastic Boolean function evaluation problem

DOI10.1007/978-3-031-18367-6_10arXiv2208.03810OpenAlexW4312412162MaRDI QIDQ6176559

Lisa Hellerstein, R. Teal Witter, Devorah Kletenik, Naifeng Liu

Publication date: 25 July 2023

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel recognition of series-parallel graphs
• Sequential testing of complex systems: a review
• Non-adaptive stochastic score classification and explainable halfspace evaluation
• Finding optimal satisficing strategies for and-or trees
• Concentration Inequalities
• Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Stochastic Covering and Adaptivity
• Algebraic properties of the LambertWfunction from a result of Rosenlicht and of Liouville
• Learning with attribute costs
• Optimal allocation of components in parallel–series and series–parallel systems
• Algorithms and Adaptivity Gaps for Stochastic Probing
• Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
• Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
• A General Framework for Approximating Min Sum Ordering Problems
• Analysis of Boolean Functions
• Stochastic Submodular Cover with Limited Adaptivity