Group testing algorithms: bounds and simulations

Abstract

We consider the problem of non-adaptive noiseless group testing of $N$ items of which $K$ are defective. We describe four detection algorithms: the COMP algorithm of Chan et al.; two new algorithms, DD and SCOMP, which require stronger evidence to declare an item defective; and an essentially optimal but computationally difficult algorithm called SSS. By considering the asymptotic rate of these algorithms with Bernoulli designs we see that DD outperforms COMP, that DD is essentially optimal in regimes where $K\ge \sqrt{N}$, and that no algorithm with a nonadaptive Bernoulli design can perform as well as the best non-random adaptive designs when $K>N^{0.35}$. In simulations, we see that DD and SCOMP far outperform COMP, with SCOMP very close to the optimal SSS, especially in cases with larger $K$.

References in corpus (3)

• The Capacity of Adaptive Group Testing
• Non-adaptive Group Testing: Explicit bounds and novel algorithms
• Adaptive group testing as channel coding with feedback

Cited by in corpus (33)

• The Capacity of Adaptive Group Testing
• A Compressed Sensing Approach to Pooled RT-PCR Testing for COVID-19 Detection
• Performance of group testing algorithms with near-constant tests-per-item
• Individual testing is optimal for nonadaptive group testing in the linear regime
• Information-theoretic and algorithmic thresholds for group testing
• Near-Optimal Noisy Group Testing via Separate Decoding of Items
• The capacity of non-identical adaptive group testing
• Optimal group testing
• The capacity of Bernoulli nonadaptive group testing
• Almost Separable Matrices
• Rates of adaptive group testing in the linear regime
• Improved group testing rates with constant column weight designs
• Strong converses for group testing in the finite blocklength regime
• Improved bounds for noisy group testing with constant tests per item
• On the optimality of some group testing algorithms
• On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing
• Pooled testing to isolate infected individuals
• A Fast Binary Splitting Approach to Non-Adaptive Group Testing
• Near optimal sparsity-constrained group testing: improved bounds and algorithms
• On the All-Or-Nothing Behavior of Bernoulli Group Testing
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Model-Based and Graph-Based Priors for Group Testing
• Concomitant Group Testing
• Small error algorithms for tropical group testing
• Learning Erdős-Rényi Random Graphs via Edge Detecting Queries
• Optimal Nested Test Plan for Combinatorial Quantitative Group Testing
• A negative binomial approximation in group testing
• Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
• Improved Bounds and Algorithms for Sparsity-Constrained Group Testing
• Nearly Optimal Sparse Group Testing
• Hypothesis Test for Bounds on the Size of Random Defective Set
• Dynamic Batching of Online Arrivals to Leverage Economies of Scale
• Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing