2013 | OriginalPaper | Buchkapitel
Threshold and Majority Group Testing
verfasst von : Rudolf Ahlswede, Christian Deppe, Vladimir Lebedev
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
We consider two generalizations of group testing: threshold group testing (introduced by Damaschke [11]) and majority group testing (a further generalization, including threshold group testing and a model introduced by Lebedev [20]).
We show that each separating code gives a nonadaptive strategy for threshold group testing for some parameters. This is a generalization of a result in [4] on “guessing secrets”, introduced in [9].
We introduce threshold codes and show that each threshold code gives a nonadaptive strategy for threshold group testing. Threshold codes include also the construction of [6]. In contrast to [8], where the number of defectives is bounded, we consider the case when the number of defectives are known. We show that we can improve the rate in this case.
We consider majority group testing if the number of defective elements is unknown but bounded (otherwise it reduces to threshold group testing). We show that cover-free codes and separating codes give strategies for majority group testing. We give a lower bound for the rate of majority group testing.