Simple algorithms for stochastic score classification with small approximation ratios

DOI10.1137/22m1523492MaRDI QIDQ6573003

Kevin Schewior, Benedikt M. Plank

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

• Unnamed Item
• Evaluation of monotone DNF formulas
• Query strategies for priced information
• An optimum testing algorithm for some symmetric coherent systems
• Sequential testing of complex systems: a review
• Diagnosing double regular systems
• The stochastic Boolean function evaluation problem for symmetric Boolean functions
• Algorithms for the unit-cost stochastic score classification problem
• Non-adaptive stochastic score classification and explainable halfspace evaluation
• Finding optimal satisficing strategies for and-or trees
• Learning with attribute costs
• Optimal Testing Procedures for Special Structures of Coherent Systems
• Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
• Some Reliability Fault-Testing Models
• Adaptivity gaps for the stochastic Boolean function evaluation problem

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