کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1149293 957870 2011 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding at least one excellent element in two rounds
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Finding at least one excellent element in two rounds
چکیده انگلیسی
Suppose that some elements of the set [n]= {1,2,…,n} are excellent. Their number and positions are unknown. Subsets of [n] can be used for tests. If this test is A⊂[n] then the result of the test is YES if at least one of the excellent ones is in A. Otherwise the answer is NO. The goal of the search is to find at least one of the excellent elements, or to claim that there is none. We prove that the number of tests is at least n in the non-adaptive case. On the other hand, if two rounds can be used then the number of tests in the worst case is at least (2+o(1))n, and this is sharp.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Statistical Planning and Inference - Volume 141, Issue 8, August 2011, Pages 2946-2952
نویسندگان
,