Name
Abstract | ||
|---|---|---|
Suppose that we are given a set of n elements d of which are "defective". A group test can check for any subset, called a pool, whether it contains a defective. It is well known that d defectives can be found by using O(d log n) pools. This nearly optimal number of pools can be achieved in 2 stages, where tests within a stage are done in parallel. But then d must be known in advance. Here we explore group testing strategies that use a nearly optimal number of pools and a few stages although d is not known to the searcher. One easily sees that O(log d) stages are sufficient for a strategy with O(d log n) pools. Here we prove a lower bound of Ω(log d/ log log d) stages and a more general pools vs. stages tradeoff. As opposed to this, we devise a randomized strategy that finds d defectives using O(d log(n/d)) pools in 3 stages, with any desired probability 1 - Ɛ. Open questions concern the optimal constant factors and practical implications. A related problem motivated by, e.g., biological network analysis is to learn hidden vertex covers of a small size k in unknown graphs by edge group tests. (Does a given subset of vertices contain an edge?)We give a 1-stage strategy using O(k3 log n) pools, with any FPT algorithm for vertex cover enumeration as a decoder. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03409-1_9 | fundamentals of computation theory |
Keywords | DocType | Volume |
1-stage strategy,minimum adaptivity,hidden vertex,edge group test,log n,group testing strategy,nonadaptive group testing,combinatorial search,optimal number,randomization.,log log,n element,stages tradeoff,group test,competitive group testing,k3 log n,randomization | Conference | 2 |
Issue | ISSN | ISBN |
3 | 0302-9743 | 3-642-03408-X |
Citations | PageRank | References |
9 | 0.71 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Damaschke | 1 | 471 | 56.99 |
| Azam Sheikh Muhammad | 2 | 34 | 4.45 |