### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. och Sheikh Muhammad, A. (2009) *Competitive group testing and learning hidden vertex covers with minimum adaptivity*.

** BibTeX **

@conference{

Damaschke2009,

author={Damaschke, Peter and Sheikh Muhammad, Azam},

title={Competitive group testing and learning hidden vertex covers with minimum adaptivity},

booktitle={17th International Symposium on Fundamentals of Computation Theory FCT 2009, Lecture Notes in Computer Science},

isbn={978-364203408-4},

pages={84-95},

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 O(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. 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, with any FPT algorithm for vertex
cover enumeration as a decoder. },

year={2009},

keywords={competitive group testing, nonadaptive strategy, adversary, randomization, vertex cover},

}

** RefWorks **

RT Conference Proceedings

SR Print

ID 97556

A1 Damaschke, Peter

A1 Sheikh Muhammad, Azam

T1 Competitive group testing and learning hidden vertex covers with minimum adaptivity

YR 2009

T2 17th International Symposium on Fundamentals of Computation Theory FCT 2009, Lecture Notes in Computer Science

SN 978-364203408-4

SP 84

OP 95

AB 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 O(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. 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, with any FPT algorithm for vertex
cover enumeration as a decoder.

LA eng

DO 10.1007/978-3-642-03409-1_9

OL 30