A NEW COMPETITIVE ALGORITHM FOR GROUP-TESTING

Algorithms for the group testing problem when there is no a priori inf ormation on the number of defective items are considered. The efficien cy criterion used is the competitive ratio, which is the ratio of the number of tests required by an algorithm when there is no a priori inf ormation on the number of defective items, to the number of tests requ ired by an optimal algorithm when the number of defective items is kno wn in advance. A new algorithm is presented, and it is shown that the competitive ratio of this algorithm is 2. This result is an improvemen t over a previous algorithm due to Du and Hwang (1990) the competitive ratio of which is 2.75. It also proves a conjecture made by Du and Hw ang. A new application of group testing techniques for high-speed netw ork is discussed.