BOUNDS FOR NONADAPTIVE GROUP TESTS TO ESTIMATE THE AMOUNT OF DEFECTIVES
Abstract
Group testing is the problem of finding d defectives in a set of n elements, by asking carefully chosen subsets (pools) whether they contain defectives. Strategies are preferred that use both a small number of tests close to the information-theoretic lower bound d log2 n, and a small constant number of stages, where tests in every stage are done in parallel, in order to save time. They should even work if d is not known in advance. In fact, one can succeed with O(d log n) queries in two stages, if certain tests are randomized and a constant failure probability is allowed. An essential ingredient of such strategies is to get an estimate of d within a constant factor. This problem is also interesting in its own right. It can be solved with O(log n) randomized group tests of a certain type. We prove that Ω(log n) tests are also necessary, if elements for the pools are chosen independently. The proof builds upon an analysis of the influence of tests on the searcher's ability to distinguish between any two candidate numbers with a constant ratio. The next challenge is to get optimal constant factors in the O(log n) test number, depending on the prescribed error probability and the accuracy of d. We give practical methods to derive upper bound tradeoffs and conjecture that they are already close to optimal. One of them uses a linear programming formulation.
This is an extended version of a paper that appeared in preliminary form in the Proceedings of the 4th International Conference on Combinatorial Optimization and Applications COCOA 2010, Big Island, Hawaii, Lecture Notes in Computer Science (Springer) 6509, pages 117–130.
