• 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