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)

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