Ratewise-optimal non-sequential search strategies under constraints on the tests |
| |
Authors: | Rudolf Ahlswede |
| |
Institution: | aFakultät für Mathematik, Universität Bielefeld, Postfach 100131, D-33501 Bielefeld, Germany |
| |
Abstract: | Already in his Lectures on Search A. Rényi, Lectures on the theory of search, University of North Carolina, Chapel Hill, Institute of Statistics, Mimeo Series No. 6007, 1969. 11]] Renyi suggested to consider a search problem, where an unknown is to be found by asking for containment in a minimal number m(n,k) of subsets A1,…,Am with the restrictions |Ai|k<n/2 for i=1,2,…,m.Katona gave in 1966 the lower bound m(n,k)logn/h(k/n) in terms of binary entropy and the upper bound m(n,k)(logn+1)/logn/k·n/k, which was improved by Wegener in 1979 to m(n,k)logn/logn/k(n/k-1).We prove here for k=pn that m(n,k)=logn+o(logn)/h(p), that is, ratewise optimality of the entropy bound: .Actually this work was motivated by a more recent study of Karpovsky, Chakrabarty, Levitin and Avresky of a problem on fault diagnosis in hypercubes, which amounts to finding the minimal number M(n,r) of Hamming balls of radius r=ρn with in the Hamming space , which separate the vertices. Their bounds on M(n,r) are far from being optimal. We establish bounds implyingHowever, it must be emphasized that the methods of prove for our two upper bounds are quite different. |
| |
Keywords: | Search strategies |
本文献已被 ScienceDirect 等数据库收录! |
|