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

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

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Abstract / Bemerkung
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.
Stichworte
Erscheinungsjahr
Zeitschriftentitel
Discrete Applied Mathematics
Band
156
Zeitschriftennummer
9: Special Issue
Seite
1431-1443
ISSN
PUB-ID

Zitieren

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. doi:10.1016/j.dam.2006.06.013
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.