On the optimality of some group testing algorithms

We consider Bernoulli nonadaptive group testing with k = Θ(η
^θ
) defectives, for θ ϵ (0,1). The practical definite defectives (DD) detection algorithm is known to be optimal for θ > 1/2. We give a new upper bound on the rate of DD, showing that DD is strictly suboptimal for θ <; 0.41. We also show that the SCOMP algorithm and algorithms based on linear programming achieve a rate at least as high as DD, so in particular are also optimal for θ ≥ 1/2.