Abstract-We study the group testing of a set of N items each of which is defective with probability p. We focus on the double limit of small defect probability, p 1, and large number of variables, N 1, taking either p ! 0 after N ! 1 or p = 1=N with 2 (0; 1=2). In both settings the optimal number of tests which are required to identify with certainty the defectives via a two-stage procedure, T(N;p), is known to scale as Npj log pj. Here we determine the sharp asymptotic value of T(N;p)=(Npj log pj) and construct a class of two-stage algorithms over which this optimal value is attained. This is done by choosing a proper bipartite regular graph (of tests and variable nodes) for the first stage of the detection. Furthermore we prove that this optimal value is also attained on average over a random bipartite graph where all variables have the same degree and the tests connected to a given variable are randomly chosen with uniform distribution among all tests. Finally, we improve the existing upper and lower bounds for the optimal number of tests in the case p = 1=N with 2 [1=2; 1).
A bipartite graph structure is considered in REF with a two-stage hybrid detection method.
Group Testing With Random Pools: Optimal Two-Stage Algorithms
IEEE Transactions on Information Theory
IEEE Transactions on Information Theory
Computer Science Physics Mathematics