Advertisement
Published in:
2013 | OriginalPaper | Chapter
Density-Based Group Testing
Authors : Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Gábor Wiener
Published in: Information Theory, Combinatorics, and Search Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we study a new, generalized version of the well-known group testing problem. In the classical model of group testing we are given
n
objects, some of which are considered to be defective. We can test certain subsets of the objects whether they contain at least one defective element. The goal is usually to find all defectives using as few tests as possible. In our model the presence of defective elements in a test set
Q
can be recognized if and only if their number is large enough compared to the size of
Q
. More precisely for a test
Q
the answer is
yes
if and only if there are at least
α
|
Q
| defective elements in
Q
for some fixed
α
.