KIAM Main page Web Library  •  Publication Search   
Publication

, 2002
Publisher:
IEEE Trans. Inform. Theory, vol.48, no. 7, 1741-1749, 2002
Authors: Berger T., Levenshtein V.I.
Asymptotical efficiency of two-stage testing
Abstract:
We adapt methods originally developed in information and coding theory to solve some testing problems. The efficiency of two-stage pool testing of n items is characterized by the minimum expected number E(n,p) of tests for the Bernoulli p-scheme, where the minimum is taken over a matrix that specifies the tests that constitute the first stage. An information-theoretic bound implies that the natural desire to achieve E(n,p)=o(n) as n → ∞ can be satisfied only if p(n) → 0. Using random selection and linear programming, we bound some parameters of binary matrices, thereby determining up to positive constants how the asymptotic behavior of E(n,p) as n → ∞ depends on the manner in which p(n) → 0. In particular,   it is shown that for p(n)=n-β+o(1), where 0<β<1, the asymptotic efficiency of two-stage procedures cannot be improved upon by generalizing to the class of all multistage adaptive testing algorithms.
Keywords:
cover-free codes, disjunctive testing, linear programming, pool testing, random selection, reconstruction algorithms, screening.
Publication language: english, pages: 8
Research direction:
Mathematical problems and theory of numerical methods
Source text:
  (PDF)