COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY
From MaRDI portal
Publication:3063600
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)
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
