On the Cut-off Point for Combinatorial Group Testing

Paul Fischer, N. Klasner, I. Wegener

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    The following problem is known as group testing problem for n objects. Each object can be essential (defective) or non-essential (intact). The problem is to determine the set of essential objects by asking queries adaptively. A query can be identified with a set Q of objects and the query Q is answered by 1 if Q contains at least one essential object and by 0 otherwise. In the statistical setting the objects are essential, independently of each other, with a given probability p <1 while in the combinatorial setting the number k <n of essential objects is known. The cut-off point of statistical group testing is equal to p* = 12(3 - 5), i.e., the strategy of testing each object individually minimizes the average number of queries iff p >= p* or n = 1. In the combinatorial setting the worst case number of queries is of interest. It has been conjectured that the cut-off point of combinatorial group testing is equal to alpha* = 13, i.e., the strategy of testing n - 1 objects individually minimizes the worst case number of queries iff k/n >= alpha* and k <n. Some results in favor of this conjecture are proved.
    Original languageEnglish
    JournalDiscrete Applied Mathematics
    Volume91
    Issue number1-3
    Pages (from-to)83-92
    ISSN0166-218X
    Publication statusPublished - 1999

    Fingerprint Dive into the research topics of 'On the Cut-off Point for Combinatorial Group Testing'. Together they form a unique fingerprint.

    Cite this