Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Randomized Group Testing Both Query-Optimal and Minimal Adaptive
verfasst von : Peter Damaschke, Azam Sheikh Muhammad
Erschienen in: SOFSEM 2012: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The classical group testing problem asks to determine at most
d
defective elements in a set of
n
elements, by queries to subsets that return Yes if the subset contains some defective, and No if the subset is free of defectives. By the entropy lower bound,
$\log_2\sum_{i=0}^d{n\choose i}$
tests, which is essentially
d
log
2
n
, are needed at least. We devise group testing strategies that combine two features: They achieve this optimal query bound asymptotically, with a factor 1 +
o
(1) as
n
grows, and they work in a fixed number of stages of parallel queries. Our strategies are randomized and have a controlled failure probability, i.e., constant but arbitrarily small. We consider different settings (known or unknown
d
, probably correct or verified outcome), and we aim at the smallest possible number of stages. In particular, 2 stages are sufficient if
d
grows slowly enough with
n
, and 4 stages are sufficient if
d
=
o
(
n
).