We consider sequential testing problems that involve a system of \(n\) stochastic components, each of which is either working or faulty with independent probability. The overall state of the system is a function of the state of its individual components, and the goal is to determine the system state by testing its components at the minimum expected cost. In the classic setting, where each component is tested separately, sequential testing algorithms are known for several functions such as AND, \(k\)-of-\(n\) and score-classification. Moreover, many of these algorithms are “non adaptive”, i.e., they test components in an a priori fixed order until the function is evaluated. We consider a batched setting that allows for testing multiple components simultaneously, at the expense of an extra setup cost. Our main result is a generic method that transforms a non-adaptive solution for the classic setting into a solution for the more general batched setting, while incurring only an additive \(\frac1{\sqrt{2}}\) loss in the approximation ratio. Combined with previously-known approximation algorithms in the classic setting, we obtain batched algorithms for AND, \(k\)-of-\(n\) and score-classification functions with approximation ratios 1.707, 2.618 and 6.371 respectively. Our algorithm is also very efficient, running in \(O(n^2)\) time for all the aforementioned functions. Finally, we evaluate the practical performance of our algorithm on random instances and observe that it performs very well in comparison to an exact (exponential time) dynamic programming method.
A General Framework for Sequential Batch-Testing
\(\)