| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1149293 | Journal of Statistical Planning and Inference | 2011 | 7 Pages |
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
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Gyula O.H. Katona,