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

Abstract

We define a variant of k-of-n testing that we call conservative k-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 Kodialam and Condon et al., who presented combinatorial algorithms for parallel pipelined filter ordering, which is the special case where k=1 (or k = n). We also consider the problem of maximizing throughput for standard k-of-n testing, and show how to obtain a polynomial-time algorithm based on the ellipsoid method using previous techniques.

17 pages. An extended abstract of this paper appeared in the Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011)