MODIFICATIONS OF COMPETITIVE GROUP-TESTING

Many fault-detection problems fall into the following model: There is a set of n items, some of which are defective. The goal is to identify the defective items by using the minimum number of tests. Each test is on a subset of items and tells whether the subset contains a defective item or not. Let M(alpha) (d, n)(M. (d\n)) denote the maximum number of tests for an algorithm alpha to identify d defectives from a set of n items provided that d, the number of defective items, is known (unknown) before the testing. Let M(d, n) = min(alpha) M(alpha) (d, n). An algorithm alpha is called a competitive algorithm if there exist constants c and a such that for all n > d > 0, M(alpha)(d\n) less-than-or-equal-to cM(d, n) + alpha. This paper confirms a recent conjecture that there exists a bisecting algorithm A such that M(A)(d\n) less-than-or-equal-to 2M(d, n) + 1. Also, an algorithm B such that M(B)(d\n) less-than-or-equal-to 1.65 M(d, n) + 10 is presented.