Name
Abstract | ||
|---|---|---|
The classical group testing problem asks to determine at most d defective elements in a set of n elements, by queries to subsets that return Yes if the subset contains some defective, and No if the subset is free of defectives. By the entropy lower bound, $\log_2\sum_{i=0}^d{n\choose i}$ tests, which is essentially d log2 n , are needed at least. We devise group testing strategies that combine two features: They achieve this optimal query bound asymptotically, with a factor 1+o (1) as n grows, and they work in a fixed number of stages of parallel queries. Our strategies are randomized and have a controlled failure probability, i.e., constant but arbitrarily small. We consider different settings (known or unknown d , probably correct or verified outcome), and we aim at the smallest possible number of stages. In particular, 2 stages are sufficient if d grows slowly enough with n , and 4 stages are sufficient if d =o (n ). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-27660-6_18 | SOFSEM |
Keywords | Field | DocType |
smallest possible number,different setting,log2 n,controlled failure probability,optimal query,defective element,minimal adaptive,randomized group,classical group testing problem,fixed number,n element,group testing strategy,group testing,randomized algorithm,algorithmic learning theory,bioinformatics | Discrete mathematics,Randomized algorithm,Algorithmic learning theory,Combinatorics,Upper and lower bounds,Group tests,Classical group,Group testing,Mathematics | Conference |
Volume | ISSN | Citations |
7147 | 0302-9743 | 11 |
PageRank | References | Authors |
0.51 | 17 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Damaschke | 1 | 471 | 56.99 |
| Azam Sheikh Muhammad | 2 | 34 | 4.45 |