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

Lisa Hellerstein, Özgür Özkan, Linda Sellie

    Research output: Contribution to journalArticlepeer-review


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

    Original languageEnglish (US)
    Pages (from-to)595-618
    Number of pages24
    Issue number2
    StatePublished - Feb 1 2017


    • Maximum throughput
    • Sequential testing
    • k-of-n testing

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


    Dive into the research topics of 'Max-Throughput for (Conservative) k-of-n Testing'. Together they form a unique fingerprint.

    Cite this