Hypergeometric group testing algorithms

Given a finite population P consisting of g good and d defective objects, the problems of hypergeometric group testing (HGT) is concerned with the identification of the d defectives by means of the following test procedure. Any subset X⊂P can be tested with two possible results: (1) either all elements of X are good, or (2) at least one element of X is defective. In the latter case, we have no knowledge as to which ones or how many are defective. In recent years, various algorithms have been proposed to solve this problem with the aim of minimizing the maximum number of tests required. However, no optimal algorithm is known at present for general g and d> 1.

We define an algorithm s to solve the HGT problem to be an l-set algorithm if throughout the entire process of implementing s, we only need to partition the still unclassified elements of P into at most l sets (P₁. ... P_l) where objects in each P_i need not be differentiated from one another. Restricting s to be an l-set algorithm limits the range of useful tests we can make as the amount of information we can keep after each successive tests depends on l. We show that all previously known HGT algorithms are either 1 or 2-set algorithms. By increasing l, we are able to construct some new classes of HGT algorithms which are more efficient than all previously known algorithms. Finally, we are able to construct optimal HGT algorithms for l≤3.