Ratewise-optimal non-sequential search strategies under constraints on the tests

Ahlswede R (2008)
Discrete Applied Mathematics 156(9: Special Issue): 1431-1443.

Journal Article | Published | English

No fulltext has been uploaded

Abstract
Already in his Lectures on Search [A. Rdnyi, 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 x is an element of X = {1, 2, ..., n} is to be found by asking for containment in a minimal number m(n, k) of subsets A(1),...,A(m) with the restrictions vertical bar A(i)vertical bar <= k < n/2 for i = 1, 2,..., m. Katona gave in 1966 the lower bound m(n, k) >= log n/h (k/n) in terms of binary entropy and the upper bound m(n, k) <= inverted right perpendicular log n + 1) / log n/k inverted left perpendicular which was improved by Wegener in 1979 to m(n, k) <= inverted right perpendicular log n / log n/k inverted left perpendicular (inverted right perpendicular n/k inverted left perpendicular - 1). We prove here for k=pn that m (n, k)=log n+o(log n)/h (p), that is, ratewise optimality of the entropy bound: lim(n ->infinity) m (n, pn)/logn = 1/h(p). 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 = rho n with rho <= 1/2 in the Hamming space H-n = {0, 1}(n), which separate the vertices. Their bounds on M(n, r) are far from being optimal. We establish bounds implying lim(n ->infinity) 1/n log M(n, r) = 1 - h(rho). However, it must be emphasized that the methods of prove for our two upper bounds are quite different. (C) 2007 Elsevier B.V. All rights reserved.
Publishing Year
ISSN
PUB-ID

Cite this

Ahlswede R. Ratewise-optimal non-sequential search strategies under constraints on the tests. Discrete Applied Mathematics. 2008;156(9: Special Issue):1431-1443.
Ahlswede, R. (2008). Ratewise-optimal non-sequential search strategies under constraints on the tests. Discrete Applied Mathematics, 156(9: Special Issue), 1431-1443.
Ahlswede, R. (2008). Ratewise-optimal non-sequential search strategies under constraints on the tests. Discrete Applied Mathematics 156, 1431-1443.
Ahlswede, R., 2008. Ratewise-optimal non-sequential search strategies under constraints on the tests. Discrete Applied Mathematics, 156(9: Special Issue), p 1431-1443.
R. Ahlswede, “Ratewise-optimal non-sequential search strategies under constraints on the tests”, Discrete Applied Mathematics, vol. 156, 2008, pp. 1431-1443.
Ahlswede, R.: Ratewise-optimal non-sequential search strategies under constraints on the tests. Discrete Applied Mathematics. 156, 1431-1443 (2008).
Ahlswede, Rudolf. “Ratewise-optimal non-sequential search strategies under constraints on the tests”. Discrete Applied Mathematics 156.9: Special Issue (2008): 1431-1443.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar