Title of article
Finding at least one excellent element in two rounds
Author/Authors
Katona، نويسنده , , Gyula O.H.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2011
Pages
7
From page
2946
To page
2952
Abstract
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.
Keywords
Search problem , Two rounds , Transversal
Journal title
Journal of Statistical Planning and Inference
Serial Year
2011
Journal title
Journal of Statistical Planning and Inference
Record number
2221531
Link To Document