Optimal deterministic group testing algorithms to estimate the number of defectives

DOI10.1016/J.TCS.2021.05.011MaRDI QIDQ5918294zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty, Catherine A. Haddad-Zaknoon

Publication date 22 June 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

deterministic group testinggroup testingpooling design

Mathematics Subject Classification ID

Combinatorial probability (60C05) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: We study the problem of estimating the number of defective items $d$ within a pile of $n$ elements up to a multiplicative factor of $Delta>1$, using deterministic group testing algorithms. We bring lower and upper bounds on the number of tests required in both the adaptive and the non-adaptive deterministic settings given an upper bound $D$ on the defectives number. For the adaptive deterministic settings, our results show that, any algorithm for estimating the defectives number up to a multiplicative factor of $Delta$ must make at least $Omegaleft((D/Delt{a}^2)log(n/D)ight)$ tests. This extends the same lower bound achieved in cite{ALA17} for non-adaptive algorithms. Moreover, we give a polynomial time adaptive algorithm that shows that our bound is tight up to a small additive term. For non-adaptive algorithms, an upper bound of $O((D/Delt{a}^2)$ $(log(n/D)+logDelta))$ is achieved by means of non-constructive proof. This improves the lower bound $O((logD)/(logDelta))Dlogn)$ from cite{ALA17} and matches the lower bound up to a small additive term. In addition, we study polynomial time constructive algorithms. We use existing polynomial time constructible emph{expander regular bipartite graphs}, emph{extractors} and emph{condensers} to construct two polynomial time algorithms. The first algorithm makes $O((D^{1+o(1)}/Delt{a}^2)cdotlogn)$ tests, and the second makes $(D/Delt{a}^2)cdotquazipoly$ $(logn)$ tests. This is the first explicit construction with an almost optimal test complexity.

Recommendations

• Adaptive group testing algorithms to estimate the number of defectives
• Bounds for nonadaptive group tests to estimate the amount of defectives
• Bounds for nonadaptive group tests to estimate the amount of defectives
• Bounds for the number of tests in non-adaptive randomized algorithms for group testing
• Randomized group testing both query-optimal and minimal adaptive

Cites work

• A group testing method for finding patterns in data
• A Method for Detecting All Defective Members in a Population by Group Testing
• A Sequential Method for Screening Experimental Variables
• Adaptive group testing algorithms to estimate the number of defectives
• An efficient FPRAS type group testing procedure to approximate the number of defectives
• Born again group testing: Multiaccess communications
• Bounds for nonadaptive group tests to estimate the amount of defectives
• Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity
• scientific article; zbMATH DE number 823957 (Why is no real title available?)
• scientific article; zbMATH DE number 5262869 (Why is no real title available?)
• Noise-resilient group testing: limitations and constructions
• Nonrandom binary superimposed codes
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Queries and concept learning
• Randomness conductors and constant-degree lossless expanders

Cited in

(8)

• Bounds for nonadaptive group tests to estimate the amount of defectives
• Bounds for nonadaptive group tests to estimate the amount of defectives
• An efficient randomized group testing procedure to determine the number of defectives
• Adaptive group testing algorithms to estimate the number of defectives
• Smart elements in combinatorial group testing problems with more defectives
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Static Risk-Based Group Testing Schemes Under Imperfectly Observable Risk
• Estimation of the Proportion of Defective Units by Using Group Testing Under the Existence of a Threshold of Detection

This page was built for publication: Optimal deterministic group testing algorithms to estimate the number of defectives

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