Identifying defective sets using queries of small size

Benevides, Fabrício S. and Gerbner, Dániel and Palmer, Cory and Vu, Dominik K. (2018) Identifying defective sets using queries of small size. DISCRETE MATHEMATICS, 341 (1). pp. 143-150. ISSN 0012-365X

Preview

Text d_separable_final_v5_u.pdf Download (277kB) | Preview

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. © 2017 Elsevier B.V.

Actions (login required)

Edit Item