Individual testing of independent items in optimal group testing.

We consider the group testing problem for a set of independent items I = {I sub 1,...,I sub n} when I sub i has probability p sub i of being defective and probability q sub i = 1 - p sub i of being good. The problem is to classify all items as good or defective with a minimum expected number of group tests where a group test is a test on a subset S of I with two possible outcomes: either S is "pure" (contains no defective) or S is "contaminated" (contains at least one defective, with no information provided about which or how many). No polynomial- time algorithm is known for the group testing problem even for the special case p sub i = p for all i. Hence any method which reduces the size of the problem is very helpful. In this paper we give such a method by providing a simple condition to screen items which should be tested (only) individually. This condition leads to a necessary and sufficient condition for the individual testing algorithm to be optimal, generalizing a result of Unger for the special case of identical p sub i.