Group Testing Algorithms: Bounds and Simulations

DOI10.1109/TIT.2014.2314472MaRDI QIDQ2986358zbMATH OpenOpenAlexWikidataFDO

Authors Matthew Aldridge, Leonardo Baldassini, Oliver Johnson

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.6438

Mathematics Subject Classification ID

Reliability and life testing (62N05) Analysis of algorithms (68W40)

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 $KgeqsqrtN$, 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$.

Cited in

(20)

• Group testing in bipartite graphs
• A group testing problem for hypergraphs of bounded rank
• On the construction of unbiased estimators for the group testing problem
• Generalized framework for group testing: queries, feedbacks and adversaries
• Random and quasi-random designs in group testing
• Strict group testing and the set basis problem
• Three-Dimensional Array-Based Group Testing Algorithms
• Noise-Resilient Group Testing: Limitations and Constructions
• Performance of Group Testing Algorithms With Near-Constant Tests Per Item
• Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms
• Information-theoretic and algorithmic thresholds for group testing
• Almost separable matrices
• Static Risk-Based Group Testing Schemes Under Imperfectly Observable Risk
• Group Testing With Random Pools: Optimal Two-Stage Algorithms
• Optimal group testing
• scientific article; zbMATH DE number 7758315 (Why is no real title available?)
• Flexible, efficient, and accurate tests for epidemics
• Non-iterative sparse signal recovery algorithms for sparse matrices and their guarantees
• Dynamic batching of online arrivals to leverage economies of scale
• A negative binomial approximation in group testing

This page was built for publication: Group Testing Algorithms: Bounds and Simulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986358)