A Group Testing Problem
Authors:
- Gerard J. ChangGCGerard J. Chang
- F. K. HwangFHF. K. Hwang
- 1 March 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 1 (1) , 21-24
Abstract
Suppose we have two disjoint sets of items of cardinalities m and n where each set contains exactly one defective item. A group test is a simultaneous test on an arbitrary group of items with two possible outcomes: The group is identified as good if it contains no defective items; otherwise it is identified as defective. The problem is to find the two defective items with a worst-case minimum number of (group) tests.The first question is whether there is anything to be gained by considering the two sets together. The answer is a somewhat surprising “yes.” The second question is this: Since there are $mn$ possible pairs of defective items,can we always solve the problem with $[ \log_2 mn ]$ tests—the information-theoretic lower bound where $[ x ]$ denotes the smallest integer not less than x. We conjecture that the answer is yes again and we provide partial evidence in favor of this conjecture. We also discuss several other related problems.