Constraining the number of positive responses in adaptive, non-adaptive, and two-stage group testing

DOI10.1007/S10878-015-9949-8zbMATH Open1356.90120arXiv1606.03200OpenAlexW2963624014MaRDI QIDQ346522FDOQ346522

Authors: Annalisa De Bonis 

Publication date: 29 November 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Abstract: Group testing is a well known search problem that consists in detecting the defective members of a set of objects O by performing tests on properly chosen subsets (pools) of the given set O. In classical group testing the goal is to find all defectives by using as few tests as possible. We consider a variant of classical group testing in which one is concerned not only with minimizing the total number of tests but aims also at reducing the number of tests involving defective elements. The rationale behind this search model is that in many practical applications the devices used for the tests are subject to deterioration due to exposure to or interaction with the defective elements. In this paper we consider adaptive, non-adaptive and two-stage group testing. For all three considered scenarios, we derive upper and lower bounds on the number of "yes" responses that must be admitted by any strategy performing at most a certain number t of tests. In particular, for the adaptive case we provide an algorithm that uses a number of "yes" responses that exceeds the given lower bound by a small constant. Interestingly, this bound can be asymptotically attained also by our two-stage algorithm, which is a phenomenon analogous to the one occurring in classical group testing. For the non-adaptive scenario we give almost matching upper and lower bounds on the number of "yes" responses. In particular, we give two constructions both achieving the same asymptotic bound. An interesting feature of one of these constructions is that it is an explicit construction. The bounds for the non-adaptive and the two-stage cases follow from the bounds on the optimal sizes of new variants of d-cover free families and (p,d)-cover free families introduced in this paper, which we believe may be of interest also in other contexts.

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

Recommendations

• Efficient group testing algorithms with a constrained number of positive responses
• Adaptive group testing with a constrained number of positive responses improved
• Bounds for nonadaptive group tests to estimate the amount of defectives
• Randomized group testing both query-optimal and minimal adaptive
• Bounds for nonadaptive group tests to estimate the amount of defectives

zbMATH Keywords

adaptive algorithmsgroup testingcover free familiesnon adaptive algorithmstwo-stage algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• A Sequential Method for Screening Experimental Variables
• Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels.
• Parametrized complexity theory.
• Selective families, superimposed codes, and broadcasting on unknown radio networks. (Extended abstract)
• Efficient Group Testing Algorithms with a Constrained Number of Positive Responses
• Title not available (Why is that?)
• Nonrandom binary superimposed codes
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• On the upper bound of the size of the \(r\)-cover-free families
• Randomized group testing for mutually obscuring defectives
• Born again group testing: Multiaccess communications
• Title not available (Why is that?)
• Learning a Hidden Subgraph
• Families of finite sets in which no set is covered by the union of \(r\) others
• A new hyperelastic model for transversely isotropic solids
• Randomized group testing both query-optimal and minimal adaptive
• Explicit Non-adaptive Combinatorial Group Testing Schemes
• Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes
• Title not available (Why is that?)
• Two new perspectives on multi-stage group testing
• Non-adaptive complex group testing with multiple positive sets
• Title not available (Why is that?)
• Threshold and Majority Group Testing
• Optimal Two-Stage Algorithms for Group Testing Problems
• A Method for Detecting All Defective Members in a Population by Group Testing
• Computational Science – ICCS 2005
• Non-unique probe selection and group testing

Cited In (4)

• On optimal randomized group testing with one defective item and a constrained number of positive responses
• A class of asymptotically optimal group screening strategies with limited item participation
• An improved zig zag approach for competitive group testing
• Randomized group testing both query-optimal and minimal adaptive

This page was built for publication: Constraining the number of positive responses in adaptive, non-adaptive, and two-stage group testing

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