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

**Harvard**

Damaschke, P. och Sheikh Muhammad, A. (2011) *Bounds for nonadaptive group tests to estimate the amount of defectives*.

** BibTeX **

@article{

Damaschke2011,

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

title={Bounds for nonadaptive group tests to estimate the amount of defectives},

journal={Discrete Mathematics, Algorithms and Applications},

issn={1793-8309},

volume={3},

issue={4},

pages={517-536},

abstract={Group testing is the problem of finding d defectives in a set of n elements, by asking carefully chosen subsets (pools) whether they contain defectives. Strategies are preferred that use both a small number of tests close to the information-theoretic lower bound d log n, and a small
constant number of stages, where tests in every stage are done in parallel, in order to save time. They should even work if d is not known in advance. In fact, one can succeed with O(d log n) queries in two stages, if certain tests are randomized and a constant failure probability is allowed. An essential ingredient of such strategies is to get an estimate of d within a constant factor. This problem is also interesting in its own right. It can be solved with O(log n) randomized group tests of a certain type. We prove
that O(log n) tests are also necessary, if elements for the pools are chosen independently. The proof builds upon an analysis of the influence of tests on the searcher's ability to distinguish between any two candidate numbers with a constant ratio. The next challenge is to get optimal constant factors in the O(log n) test number, depending on the prescribed error probability and the accuracy of d. We give practical methods to derive upper bound tradeoffs and conjecture that they are already close to optimal. One of them uses a linear programming formulation.},

year={2011},

keywords={group testing, combinatorial search, learning by queries, nonadaptive strategy, competitive ratio, randomization, linear program, lower bound},

}

** RefWorks **

RT Journal Article

SR Print

ID 151814

A1 Damaschke, Peter

A1 Sheikh Muhammad, Azam

T1 Bounds for nonadaptive group tests to estimate the amount of defectives

YR 2011

JF Discrete Mathematics, Algorithms and Applications

SN 1793-8309

VO 3

IS 4

SP 517

OP 536

AB Group testing is the problem of finding d defectives in a set of n elements, by asking carefully chosen subsets (pools) whether they contain defectives. Strategies are preferred that use both a small number of tests close to the information-theoretic lower bound d log n, and a small
constant number of stages, where tests in every stage are done in parallel, in order to save time. They should even work if d is not known in advance. In fact, one can succeed with O(d log n) queries in two stages, if certain tests are randomized and a constant failure probability is allowed. An essential ingredient of such strategies is to get an estimate of d within a constant factor. This problem is also interesting in its own right. It can be solved with O(log n) randomized group tests of a certain type. We prove
that O(log n) tests are also necessary, if elements for the pools are chosen independently. The proof builds upon an analysis of the influence of tests on the searcher's ability to distinguish between any two candidate numbers with a constant ratio. The next challenge is to get optimal constant factors in the O(log n) test number, depending on the prescribed error probability and the accuracy of d. We give practical methods to derive upper bound tradeoffs and conjecture that they are already close to optimal. One of them uses a linear programming formulation.

LA eng

OL 30