Paul Fischer, Norbert Klasner, Ingo Wegener:
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^* = {1 \over 2}(3-\sqrt{5})$,
i.e., the strategy of testing each object individually minimizes the
average number of queries iff $p \geq p^*$ or $n = 1$. In the
combinatorial setting the worst case number of queries is of interest.
Here the conjecture is established that the cut-off point of
combinatorial group testing is equal to $\alpha^* = {1 \over 3}$,
i.e., the strategy of testing $n-1$ objects individually minimizes the
worst case number of queries iff $k/n \geq \alpha^*$. Some results in
favor of this conjecture are proved.
Last update: 11/17/98. Norbert Klasner, klasner@lmi.ruhr-uni-bochum.de.
Return to list of my publications.