KIAM Main page Web Library  •  Publication Search  Русский 
Publication

, 2003
Publisher:
Discrete Mathematics,vol.266, no.1, 293-309, 2003
Authors: Levenshtein V.I.
A universal bound for a covering in regular posets and its application to pool testing
Abstract:
Let V(n) be the set of all 2n subsets of the set Nn={1,2,...,n} and Vi(n)={x∈V(n):|x|=i}. For a fixed i=1,...,n, consider a covering operator F : Vi(n)→ V(n) such that x⊆ F(x) for any x∈ Vi(n). Let C={F(x):x∈Vi(n)}. Using averaging and linear programming it is found an upper bound on the mean value |F(x)| over all x∈Vi(n) which is attained if and only if C is a Steiner S(i,{k,k+1},n) design with a specified distance distribution. A generalization of this result to the case of monotone left-regular n-posets is given. One of motivating applications is the problem of reconstructing an unknown binary vector x of length n using pool testing under the condition that the vectors x are distributed with probabilities p|x|(1-p)n-|x| where x∈V(n) denotes the indices of the ones (active items) in x. This improves upon an information theoretic bound for the minimum average number E(n,p) of tests to reconstruct an unknown x using two-stage pool testing and allows determination of the asymptotic behavior of E(n,p) up to a positive constant factor as n → ∞ under some restrictions upon p=p(n).
Keywords:
covering, poset, pool testing, Steiner system, universal bound.
Publication language: english
Research direction:
Mathematical problems and theory of numerical methods
Source text:
  (PS)