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