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\le d\le 10^6$$ 1 ≤ d ≤ 10 6 . In particular, for $$1\le d\le 10^6$$ 1 ≤ d ≤ 10 6 and the special case where n is a power of 2, we obtain an upper bound of $$d\log \frac{n}{d}+Cd+O(\log d)$$ d log n d + C d + O ( log d ) with $$C\approx 2.67$$ 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\le d\le 10^6$$ 1 ≤ d ≤ 10 6 actually hold for all $$d\ge 1$$ d ≥ 1 .