A randomized competitive group testing procedure

In many fault detection problems, we want to identify all 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 practice, the number d of defective items is often unknown in advance. In this paper, we propose a randomized group testing procedure RGT for the scenario where the number d of defectives is unknown in advance, and prove that RGT is competitive. By incorporating numerical results, we obtain improved upper bounds on the expected number of tests performed by RGT, for 1 ≤ d≤ 10 ⁶. In particular, for 1 ≤ d≤ 10 ⁶ and the special case where n is a power of 2, we obtain an upper bound of dlognd+Cd+O(logd) with C≈ 2.67 on the expected number of tests performed by RGT, which is better than the currently best upper bound in Cheng et al. (INFORMS J Comput 26(4):677–689, 2014). We conjecture that the above improved upper bounds based on numerical results from 1 ≤ d≤ 10 ⁶ actually hold for all d≥ 1.