کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903151 | 1632403 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Identifying defective sets using queries of small size
ترجمه فارسی عنوان
شناسایی مجموعه های معیوب با استفاده از پرس و جو از اندازه های کوچک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تست گروه، جستجوی ترکیبی تفکیکپذیری جداگانه، هیپرگراسیون رایگان اتحادیه،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 1, January 2018, Pages 143-150
Journal: Discrete Mathematics - Volume 341, Issue 1, January 2018, Pages 143-150
نویسندگان
FabrÃcio S. Benevides, Dániel Gerbner, Cory T. Palmer, Dominik K. Vu,