COMPETITIVE GROUP-TESTING

Let M(A)(n,d) denote the maximum number of group tests for a group tes ting algorithm A to identify d defectives from a set of n items when d is known, and let M(A)(n\d) denote the number when d is unknown. Defi ne M(n,d) = min(A) M(A)(n,d). An algorithm A is called a competitive a lgorithm if there exist constants c and a such that for all n > d grea ter-than-or-equal-to 0, M(A)(n\d) less-than-or-equal-to cM(n,d) + a. I n this paper, we present some competitive group testing algorithms.