Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
An Efficient Algorithm for Combinatorial Group Testing
verfasst von : Andreas Allemann
Erschienen in: Information Theory, Combinatorics, and Search Theory
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
In the (
d
,
n
) group testing problem
n
items have to be identified as either good or defective and the number of defective items is known to be
d
. A test on an arbitrary group (subset) of items reveals either that all items in the group are good or that at least one of the items is defective, but not how many or which items are defective. We present a new algorithm which in the worst case needs less than
$0.255d+\frac{1}{2}\log d+5.5$
tests more than the information lower bound
$\left\lceil \log\binom{n}{d}\right\rceil $
for
$\frac{n}{d}\geq2$
. For
$\frac{n}{d}\geq38$
, the difference decreases to less than
$0.187d+\frac{1}{2}\log d+5.5$
tests. For
d
≥ 10, this is a considerable improvement over the
d
− 1 additional tests given for the best previously known algorithm by Hwang. We conjecture that the behaviour for large
n
and
d
of the difference is optimal for
$\frac{n}{d}\leq4$
. This implies that the
$\frac{1}{2}-\log\frac{32}{27}=0.255$
tests per defective given in the bound above are the best possible.