Nonadaptive group testing with lies: Probabilistic existence theorems

Article English OPEN
Zhigljavsky, Anatoly Alexandrovich;

We consider a wide range of combinatorial group testing problems with lies including binary, additive and multiaccess channel group testing problems. We derive upper bounds for the number of tests in the optimal nonadaptive algorithms. The derivation is probabilistic an... View more
  • References (22)
    22 references, page 1 of 3

    [1] Ahlswede R. and Wegener I. (1987). Search Problems, Wiley and Sons, N.Y.

    [2] Alon, N., Spencer J. and Erd}os P. (1992). The Probabilistic Method, Wiley and Sons, N.Y.

    [3] Barry D.A., Parlange J.-Y., Li L., Prommer H., Cunnigham C.J. and Stagnitti F. (2000) Analytical approximations for real values of the Lambert W-function, Mathematics and Computers in Simulation, 53, 95-103.

    [4] Chen, H.-B. and Hwang, F. K. (2008) A survey on nonadaptive group testing algorithms through the angle of decoding, Journal of Combinatorial Optimization, 15, 49-59.

    [5] Corless R.M., Gonnet G.H., Hare D.E.G., Je®rey D.J. , and Knuth D.E. (1996) On the Lambert W-function, Advances in Computational Mathematics, 5, 329-359.

    [6] Deppe, C. (2006) Coding with Feedback and Searching with Lies, In: Entropy, Search, Complexity. Bolyai Society Mathematical Studies, 16. (eds I. Csisz'ar, G.O.H. Katona, G. Tardos), Springer, Berlin, 27-70.

    [7] Dorfman, R. (1943). The detection of defective numbers of large population, Ann. Math. Statist. 14, 436{440.

    [8] Du, D.Z. and Hwang, F.K. (2000) Combinatorial Group Testing, 2nd edition, World Scienti¯c, Singapore.

    [9] Du, D.Z. and Hwang, F.K. (2006) Pooling Designs and Nonadaptive Group Testing, World Scienti¯c, Singapore.

    [10] Dyachkov A.G. and Rykov V.V. (1983) A survey of superimposed code theory, Problems Control Inform. Thy. 12, 229{242.

  • Metrics
Share - Bookmark