On the cut-off point for combinatorial group testing

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 answe red by 1 if Q contains at least one essential object and by 0 otherwise. In the statistical setting the objects an essential, independently of each ot her, 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 statistica l group testing is equal to p* = 1/2(3 - root 5), i.e., the strategy of tes ting each object individually minimizes the average number of queries iff p greater than or equal to p* or n = 1. In the combinatorial setting the wor st case number of queries is of interest. It has been conjectured that the cut-off point of combinatorial group testing is equal to alpha* = 1/3, i.e. , the strategy of testing n - 1 objects individually minimizes the worst ca se number of queries iff k/n greater than or equal to alpha* and k < n. Som e results in favor of this conjecture are proved. (C) 1999 Elsevier Science B.V. All rights reserved.