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

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
    Pages703-713
    Number of pages11
    DOIs
    StatePublished - 2011
    Event22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan
    Duration: Dec 5 2011Dec 8 2011

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume7074 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other22nd International Symposium on Algorithms and Computation, ISAAC 2011
    CountryJapan
    CityYokohama
    Period12/5/1112/8/11

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Max-throughput for (conservative) k-of-n testing'. Together they form a unique fingerprint.

    Cite this