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

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

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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
    JournalAlgorithmica
    Volume77
    Issue number2
    DOIs
    StatePublished - Feb 1 2017

    Keywords

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

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

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

    Cite this