ON OPTIMAL NESTED GROUP-TESTING ALGORITHMS

Group testing was first proposed for blood testing although it has many industrial applications as well. Most of the group testing literature has studied a naturally defined class of algorithms called nested algorithms. Optimal nested algorithms are usually defined by recursive equations which do not seem to have general closed-form solutions, and so are not in general well understood. One exception is a result that gives a necessary and sufficient condition for the individual testing algorithm to be optimal. The next simplest algorithm is the pairwise testing algorithm which tests a pair of items at a time except when a pair known to contain a defective is found, then a single item from that pair is tested. In this paper we present an explicit algorithm for optimally finding a single defective in a contaminated set and use this to derive a necessary and sufficient condition for the pairwise testing algorithm to be the optimal nested algorithm. © 1990.