TY - GEN
T1 - Max-throughput for (conservative) k-of-n testing
AU - Hellerstein, Lisa
AU - Özkan, Özgür
AU - Sellie, Linda
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84055193610&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84055193610&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-25591-5_72
DO - 10.1007/978-3-642-25591-5_72
M3 - Conference contribution
AN - SCOPUS:84055193610
SN - 9783642255908
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 703
EP - 713
BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011
Y2 - 5 December 2011 through 8 December 2011
ER -