Simple algorithms for stochastic score classification with small approximation ratios

DOI10.1137/22M1523492MaRDI QIDQ6573003zbMATH OpenFDO

Authors Benedikt M. Plank, Kevin Schewior

Publication date 16 July 2024

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

Full work available at URL https://doi.org/10.1137/22M1523492

zbMATH Keywords

adaptivity gapapproximation algorithmsstochastic Boolean function evaluationstochastic score classification

Mathematics Subject Classification ID

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

Cites work

• 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
• The stochastic score classification problem

Cited in

(1)

• Non-adaptive evaluation of k-of-n functions: tight gap and a unit-cost PTAS

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)