Advertisement
Published in:
2011 | OriginalPaper | Chapter
Max-Throughput for (Conservative) k-of-n Testing
Authors : Lisa Hellerstein, Özgür Özkan, Linda Sellie
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 maximizing the throughput of conservative
k
-of-
n
testing, in a parallel setting. This extends previous work of Kodialam and Condon et al. on the parallel pipelined filter ordering problem, which is the special case where
k
= 1 (or
k
=
n
) [1,2,3]. We also consider the problem of maximizing throughput for
standard
k
-of-
n
testing, and describe a polynomial-time algorithm for it based on the ellipsoid method.