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

**Harvard**

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

** BibTeX **

@article{

Damaschke2010,

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

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

journal={Discrete Mathematics, Algorithms and Applications},

issn={1793-8309},

volume={2},

issue={3},

pages={291-311},

abstract={Suppose that we are given a set of n elements d of which
have a property called defective. A group test can check
for any subset, called a pool, whether it contains a defective. It is known that a nearly optimal number of
O(d log (n/d)) pools in 2 stages (where tests within a
stage are done in parallel) are sufficient, but then the searcher must know d 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 beforehand.
We prove a lower bound of O(log d log log d) stages and a
more general pools vs. stages tradeoff. This is almost
tight, since O(log d) stages are sufficient for a strategy with O(d log n) pools. As opposed to this negative result,
we devise a randomized strategy using O(d log (n/d)) pools
in 3 stages, with any desired success probability 1-epsilon. With some additional measures even 2 stages are enough.
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(k^3 log n) pools, with
any parameterized algorithm for vertex cover enumeration as
a decoder. During the course of this work we also provide
a classification of types of randomized search strategies
in general.},

year={2010},

keywords={nonadaptive group testing, competitive group testing, combinatorial search, randomization},

}

** RefWorks **

RT Journal Article

SR Print

ID 129203

A1 Damaschke, Peter

A1 Sheikh Muhammad, Azam

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

YR 2010

JF Discrete Mathematics, Algorithms and Applications

SN 1793-8309

VO 2

IS 3

SP 291

OP 311

AB Suppose that we are given a set of n elements d of which
have a property called defective. A group test can check
for any subset, called a pool, whether it contains a defective. It is known that a nearly optimal number of
O(d log (n/d)) pools in 2 stages (where tests within a
stage are done in parallel) are sufficient, but then the searcher must know d 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 beforehand.
We prove a lower bound of O(log d log log d) stages and a
more general pools vs. stages tradeoff. This is almost
tight, since O(log d) stages are sufficient for a strategy with O(d log n) pools. As opposed to this negative result,
we devise a randomized strategy using O(d log (n/d)) pools
in 3 stages, with any desired success probability 1-epsilon. With some additional measures even 2 stages are enough.
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(k^3 log n) pools, with
any parameterized algorithm for vertex cover enumeration as
a decoder. During the course of this work we also provide
a classification of types of randomized search strategies
in general.

LA eng

OL 30