Max-Throughput for (Conservative) k-of-n Testing

We define a variant of k-of-n testing that we call conservativek-of-n testing. We present a polynomial-time, combinatorial algorithm for the problem of maximizing throughput of conservative k-of-n testing, in a parallel setting. This extends previous work of Condon et al. and Kodialam who presented combinatorial algorithms for parallel pipelined filter ordering, which is the special case where k= 1 (or k= n). We also give a polynomial-time algorithm for maximizing throughput for standardk-of-n testing, based on the ellipsoid method, using previous techniques.