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 :
بازگشت