BOUNDS FOR NONADAPTIVE GROUP TESTS TO ESTIMATE THE AMOUNT OF DEFECTIVES

DOI10.1142/S1793830911001383zbMath1252.68138MaRDI QIDQ2905282

Peter Damaschke, Azam Sheikh Muhammad

Publication date: 27 August 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

randomization; competitive ratio; lower bound; linear program; group testing; combinatorial search; learning by queries; nonadaptive strategy

Mathematics Subject Classification ID

68Q32: Computational learning theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Learning a hidden graph, A new randomized algorithm for group testing with unknown number of defective items

Cites Work

• Exploring the missing link among \(d\)-separable, \(\overline d\)-separable and \(d\)-disjunct matrices
• Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels.
• Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis
• COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY
• Improved Results for Competitive Group Testing
• Optimal Two-Stage Algorithms for Group Testing Problems
• Improved Combinatorial Group Testing Algorithms for Real‐World Problem Sizes