Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation

Sequential testing problems involve a complex system with several components, each of which is “working” with some independent probability. The outcome of each component can be determined by performing a test, which incurs some cost. The overall system status is given by a function f of the outcomes of its components. The goal is to evaluate this function f by performing tests at the minimum expected cost. Although there has been extensive prior work on this topic, provable approximation bounds are mainly limited to simple functions, like “ k -out-of- n ” and half-spaces. We consider significantly more general “score classification” functions, and we provide the first constant-factor approximation algorithm (improving over a previous logarithmic approximation ratio). Moreover, our policy is nonadaptive; it just involves performing tests in an a priori fixed order. We also consider the related half-space evaluation problem, where we want to evaluate some function on d half-spaces (e.g., the intersection of half-spaces). We show that our approach provides an O ( d 2 log d ) -approximation algorithm for this problem. Our algorithms also extend to the setting of “batched” tests, where multiple tests can be performed simultaneously while incurring an extra setup cost. Finally, we perform computational experiments that demonstrate the practical performance of our algorithm for score classification. We observe that, for most instances, the cost of our algorithm is within a factor of 1.5 of an information-theoretic lower bound on the optimal value.