COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY

DOI10.1142/S179383091000067XzbMath1207.68158MaRDI QIDQ3063600

Peter Damaschke, Azam Sheikh Muhammad

Publication date: 15 December 2010

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

zbMATH Keywords

randomizationcombinatorial searchcompetitive group testingnonadaptive group testing

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (8)

Randomized Group Testing Both Query-Optimal and Minimal Adaptive ⋮ BOUNDS FOR NONADAPTIVE GROUP TESTS TO ESTIMATE THE AMOUNT OF DEFECTIVES ⋮ Exact learning from an honest teacher that answers membership queries ⋮ An efficient randomized group testing procedure to determine the number of defectives ⋮ Upper and lower bounds for competitive group testing ⋮ An efficient FPRAS type group testing procedure to approximate the number of defectives ⋮ Learning a hidden graph ⋮ A new randomized algorithm for group testing with unknown number of defective items

Cites Work

• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Exploring the missing link among \(d\)-separable, \(\overline d\)-separable and \(d\)-disjunct matrices
• Learning a hidden graph using \(O(\log n)\)queries per edge
• An upper bound of the number of tests in pooling designs for the error-tolerant complex model
• On the upper bound of the size of the \(r\)-cover-free families
• On parallel attribute-efficient learning.
• Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis
• Modifications of Competitive Group Testing
• Improved Results for Competitive Group Testing
• Optimal Two-Stage Algorithms for Group Testing Problems
• Learning a Hidden Subgraph
• Improved Combinatorial Group Testing Algorithms for Real‐World Problem Sizes

This page was built for publication: COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY