Competitive group testing and learning hidden vertex covers with minimum adaptivity

DOI10.1142/S179383091000067XMaRDI QIDQ3063600zbMATH OpenFDO

Authors Peter Damaschke, Azam Sheikh Muhammad

Publication date 15 December 2010

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

Full work available at URL https://doi.org/10.1142/S179383091000067X

zbMATH Keywords

randomizationcombinatorial searchcompetitive group testingnonadaptive group testing

Mathematics Subject Classification ID

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

Recommendations

• Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity
• Randomized group testing both query-optimal and minimal adaptive
• Bounds for nonadaptive group tests to estimate the amount of defectives
• Bounds for nonadaptive group tests to estimate the amount of defectives
• Two new perspectives on multi-stage group testing

Cites work

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

Cited in

(14)

• Randomized group testing both query-optimal and minimal adaptive
• A new randomized algorithm for group testing with unknown number of defective items
• Improved lower bound for estimating the number of defective items
• An efficient randomized group testing procedure to determine the number of defectives
• Bounds for nonadaptive group tests to estimate the amount of defectives
• A tight lower bound on non-adaptive group testing estimation
• Improved lower bound for estimating the number of defective items
• Exact learning from an honest teacher that answers membership queries
• An efficient FPRAS type group testing procedure to approximate the number of defectives
• Learning a hidden graph
• Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity
• Upper and lower bounds for competitive group testing
• Randomized adaptive test cover
• Consistency checking problems: a gateway to parameterized sample complexity

This page was built for publication: Competitive group testing and learning hidden vertex covers with minimum adaptivity

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