A new randomized algorithm for group testing with unknown number of defective items

In many fault detection problems, we want to identify defective items from a set of $$n$$ 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$$ d of defective items is often unknown in advance. In this paper, we propose a new randomized group testing algorithm RPT (Randomized Parallel Testing) for the case where the number $$d$$ d of defective items is unknown in advance, such that with high probability $$1-\frac{1}{(2d)^{\Omega (1)}}$$ 1 - 1 ( 2 d ) Ω ( 1 ) , the total number of tests performed by RPT is bounded from the above by $$d\log \frac{n}{d}+2d+O(d^{\frac{2}{3}}\log d)$$ d log n d + 2 d + O ( d 2 3 log d ) . If $$0