2011/09/15 by Lisa Hellerstein, Hellerstein, Lisa, Özgür Özkan +3 · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #F.2.2 #FOS: Computer and information sciences #H.2.4 #Machine Learning and Algorithms #Parallel #Software Testing and Debugging Techniques #VLSI and Analog Circuit Testing #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1109.3401
openalex publication_date 2011/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.