A class of asymptotically optimal group testing strategies to identify good items

Abstract In many fault detection problems, we want to identify all the d defective items from a set of n items using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. In this paper, we study a variant of the classical group testing problem, which we call IGI (Identifying Good Items) problem. Instead of identifying all defective items, problem IGI is to identify good items that occupy no less than a prescribed proportion f 1 in the input set. We investigate group testing strategies for problem IGI using the minimum number of tests in the worst case. A class of testing strategies for problem IGI when d is unknown in advance is proposed, and a lower bound on the worst case number of tests required by any deterministic testing strategy for problem IGI is proved. The lower bound is valid no matter whether d is known in advance or not. When f approaches one, all the testing strategies in the proposed class are asymptotically optimal, and the best ratio between the upper bounds from the proposed class and the above lower bound is 3 log 2 3 .