When is individual testing optimal for nonadaptive group testing?

Abstract

The combinatorial group testing problem is, assuming the existence of up to d defectives among n items, to identify the defectives by as few tests as possible. In this paper, we study the problem for what values of n, given d, individual testing is optimal in nonadaptive group testing. Let N (d) denote the largest n for fixed d for which individual testing is optimal. We will show that N (d) = (d + 1)(2) under a prevalent constraint in practical nonadaptive algorithms and prove that N (d) = (d + 1)(2) for d = 1, 2, 3, 4 without any constraint.