Simple algorithms for stochastic score classification with small approximation ratios

DOI10.1137/22M1523492MaRDI QIDQ6573003FDO

Authors Benedikt M. Plank, Kevin Schewior

Publication date 16 July 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsstochastic Boolean function evaluationadaptivity gapstochastic score classification

Mathematics Subject Classification ID

Search theory (90B40) Approximation algorithms (68W25)

Cites work

• scientific article; zbMATH DE number 7378706 (Why is no real title available?)
• Adaptivity gaps for the stochastic Boolean function evaluation problem
• Algorithms for the unit-cost stochastic score classification problem
• An optimum testing algorithm for some symmetric coherent systems
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Diagnosing double regular systems
• Evaluation of monotone DNF formulas
• Finding optimal satisficing strategies for and-or trees
• Learning with attribute costs
• Non-adaptive stochastic score classification and explainable halfspace evaluation
• Optimal Testing Procedures for Special Structures of Coherent Systems
• Query strategies for priced information
• Sequential testing of complex systems: a review
• Some Reliability Fault-Testing Models
• The stochastic Boolean function evaluation problem for symmetric Boolean functions

This page was built for publication: Simple algorithms for stochastic score classification with small approximation ratios

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6573003)