Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872645 | Discrete Applied Mathematics | 2012 | 10 Pages |
Abstract
Given a search space S={1,2,â¦,n}, an unknown element xââS and fixed integers ââ¥1 and qâ¥1, a q+1-ary â-restricted query is of the following form: which one of the set {A0,A1,â¦,Aq} is the xâ in?, where (A0,A1,â¦,Aq) is a partition of S and |Ai|â¤â for i=1,2,â¦,q. The problem of finding xâ from S with q+1-ary size-restricted queries is called as a q+1-ary search game with small sets. In this paper, we consider sequential algorithms for the above problem, and establish the minimum number of average-case sequential queries when xâ satisfies the uniform distribution on S.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kun Meng, Chuang Lin, Wen An Liu, Yang Yang, Gyula O.H. Katona,