Minimum average-case queries of q + 1 -ary search game with small sets

Meng, Kun and Lin, Chuang and Liu, Wen An and Yang, Yang and Katona, Gyula (2012) Minimum average-case queries of q + 1 -ary search game with small sets. DISCRETE APPLIED MATHEMATICS, 160 (4-5). pp. 618-627. ISSN 0166-218X

Preview

Text Minimum average-case queries of q + 1 -ary search game with small sets.pdf Download (340kB) | Preview

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 {A 0,A 1,...,A q} is the x* in?, where (A 0,A 1,...,A q) 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. © 2011 Elsevier B.V. All rights reserved.

Actions (login required)

Edit Item