Group Testing Algorithms: Bounds and Simulations

DOI10.1109/TIT.2014.2314472zbMATH Open1360.68970arXiv1306.6438OpenAlexW2158419847WikidataQ60522086 ScholiaQ60522086MaRDI QIDQ2986358FDOQ2986358

Authors: Matthew Aldridge, Leonardo Baldassini, Oliver Johnson 

Publication date: 16 May 2017

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

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

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

Mathematics Subject Classification ID

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

Cited In (17)

• On the construction of unbiased estimators for the group testing problem
• Three-Dimensional Array-Based Group Testing Algorithms
• Group testing in bipartite graphs
• Title not available (Why is that?)
• Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms
• Optimal group testing
• Random and quasi-random designs in group testing
• Flexible, efficient, and accurate tests for epidemics
• Static Risk-Based Group Testing Schemes Under Imperfectly Observable Risk
• Generalized framework for group testing: queries, feedbacks and adversaries
• Title not available (Why is that?)
• Noise-Resilient Group Testing: Limitations and Constructions
• Group Testing With Random Pools: Optimal Two-Stage Algorithms
• A group testing problem for hypergraphs of bounded rank
• Performance of Group Testing Algorithms With Near-Constant Tests Per Item
• Almost separable matrices
• Strict group testing and the set basis problem

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)