TY - GEN

T1 - Max-throughput for (conservative) k-of-n testing

AU - Hellerstein, Lisa

AU - Özkan, Özgür

AU - Sellie, Linda

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

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 -