Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903151 | Discrete Mathematics | 2018 | 8 Pages |
Abstract
We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set X of n elements we want to identify an unknown subset Y of X, which is known to have exactly d elements, by means of testing, for as few as possible subsets A of X, whether A intersects Y or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number k. Our main results are nearly tight bounds on the minimum number of tests necessary when d and k are fixed and n is large enough.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
FabrÃcio S. Benevides, Dániel Gerbner, Cory T. Palmer, Dominik K. Vu,