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

**Harvard**

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

** BibTeX **

@conference{

Damaschke2010,

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

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

booktitle={Lecture Notes in Computer Science. 4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010, Kailua-Kona, 18-20 December 2010},

isbn={978-3-642-17460-5},

pages={117-130},

abstract={The classical and well-studied group testing problem is to find d defectives in a set of n elements by group tests, which tell us for any chosen subset whether it contains defectives or not. 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 completely unknown in advance. An essential ingredient of such competitive and minimal-adaptive group testing strategies is an estimate of d within a constant factor. More precisely, d shall be underestimated only with some
given error probability, and overestimated only by a constant factor, called the competitive ratio. The latter problem is also interesting in its own right. It can be solved with O(log n) randomized group tests of a certain type. In this paper we prove that O(log n) tests are really needed. The proof is based on an analysis of the influence of tests on the searcher's ability to distinguish between any two candidate numbers with a constant ratio. Once we know this lower bound, the next challenge is to get optimal constant factors in the O(log n) test number, depending on the desired error probability and competitive ratio. We give a method to derive upper bounds and conjecture that our particular strategy is already optimal. },

year={2010},

keywords={algorithm, learning by queries, competitive group testing, nonadaptive strategy, randomized strategy, lower bound},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 132211

A1 Damaschke, Peter

A1 Sheikh Muhammad, Azam

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

YR 2010

T2 Lecture Notes in Computer Science. 4th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2010, Kailua-Kona, 18-20 December 2010

SN 978-3-642-17460-5

SP 117

OP 130

AB The classical and well-studied group testing problem is to find d defectives in a set of n elements by group tests, which tell us for any chosen subset whether it contains defectives or not. 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 completely unknown in advance. An essential ingredient of such competitive and minimal-adaptive group testing strategies is an estimate of d within a constant factor. More precisely, d shall be underestimated only with some
given error probability, and overestimated only by a constant factor, called the competitive ratio. The latter problem is also interesting in its own right. It can be solved with O(log n) randomized group tests of a certain type. In this paper we prove that O(log n) tests are really needed. The proof is based on an analysis of the influence of tests on the searcher's ability to distinguish between any two candidate numbers with a constant ratio. Once we know this lower bound, the next challenge is to get optimal constant factors in the O(log n) test number, depending on the desired error probability and competitive ratio. We give a method to derive upper bounds and conjecture that our particular strategy is already optimal.

LA eng

DO 10.1007/978-3-642-17461-2_10

LK http://dx.doi.org/10.1007/978-3-642-17461-2_10

OL 30