Document Open Access Logo

Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives

Authors Nader H. Bshouty, Catherine A. Haddad-Zaknoon, Raghd Boulos, Foad Moalem, Jalal Nada, Elias Noufi, Yara Zaknoon

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.18.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Author Details

Nader H. Bshouty
  • Department of Computer Science, Technion, Haifa, Israel
Catherine A. Haddad-Zaknoon
  • Department of Computer Science, Technion, Haifa, Israel
Raghd Boulos
  • The Arab Orthodox College, Haifa, Israel
Foad Moalem
  • The Arab Orthodox College, Haifa, Israel
Jalal Nada
  • The Arab Orthodox College, Haifa, Israel
Elias Noufi
  • The Arab Orthodox College, Haifa, Israel
Yara Zaknoon
  • The Arab Orthodox College, Haifa, Israel

Cite AsGet BibTex

Nader H. Bshouty, Catherine A. Haddad-Zaknoon, Raghd Boulos, Foad Moalem, Jalal Nada, Elias Noufi, and Yara Zaknoon. Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SWAT.2020.18

Abstract

We study the problem of determining the exact number of defective items in an adaptive group testing by using a minimum number of tests. We improve the existing algorithm and prove a lower bound that shows that the number of tests in our algorithm is optimal up to small additive terms.

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Mathematics of computing → Discrete mathematics
  • Mathematics of computing → Probabilistic algorithms
  • Theory of computation → Probabilistic computation
Keywords
  • Group Testing
  • Randomized Algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nader H. Bshouty. Lower bound for non-adaptive estimate the number of defective items. Electronic Colloquium on Computational Complexity (ECCC), 25:53, 2018. URL: https://eccc.weizmann.ac.il/report/2018/053.
  2. Nader H. Bshouty, Vivian E. Bshouty-Hurani, George Haddad, Thomas Hashem, Fadi Khoury, and Omar Sharafy. Adaptive group testing algorithms to estimate the number of defectives. In Algorithmic Learning Theory, ALT 2018, 7-9 April 2018, Lanzarote, Canary Islands, Spain, pages 93-110, 2018. URL: http://proceedings.mlr.press/v83/bshouty18a.html.
  3. Nader H. Bshouty, Nuha Diab, Shada R. Kawar, and Robert J. Shahla. Non-adaptive randomized algorithm for group testing. In International Conference on Algorithmic Learning Theory, ALT 2017, 15-17 October 2017, Kyoto University, Kyoto, Japan, pages 109-128, 2017. Google Scholar
  4. Chao L. Chen and William H. Swallow. Using group testing to estimate a proportion, and to test the binomial model. Biometrics., 46(4):1035-1046, 1990. Google Scholar
  5. Yongxi Cheng. An efficient randomized group testing procedure to determine the number of defectives. Oper. Res. Lett., 39(5):352-354, 2011. URL: https://doi.org/10.1016/j.orl.2011.07.001.
  6. Yongxi Cheng and Ding-Zhu Du. New constructions of one- and two-stage pooling designs. Journal Of Computational Biology, 2008. Google Scholar
  7. Yongxi Cheng, Ding-Zhu Du, and Yinfeng Xu. A zig-zag approach for competitive group testing. INFORMS Journal on Computing, 26(4):677-689, 2014. URL: https://doi.org/10.1287/ijoc.2014.0591.
  8. Yongxi Cheng, Ding-Zhu Du, and Feifeng Zheng. A new strongly competitive group testing algorithm with small sequentiality. Annals OR, 229(1):265-286, 2015. URL: https://doi.org/10.1007/s10479-014-1766-4.
  9. Yongxi Cheng, Dingzhu Du, and Guohui Lin. On the upper bounds of the minimum number of rows of disjunct matrices. Optimization Letters, 3:297-302, 2009. Google Scholar
  10. Yongxi Cheng and Yinfeng Xu. An efficient FPRAS type group testing procedure to approximate the number of defectives. J. Comb. Optim., 27(2):302-314, 2014. URL: https://doi.org/10.1007/s10878-012-9516-5.
  11. Ferdinando Cicalese. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-17327-1.
  12. Graham Cormode and S. Muthukrishnan. What’s hot and what’s not: tracking most frequent items dynamically. ACM Trans. Database Syst., 30(1):249-278, 2005. URL: https://doi.org/10.1145/1061318.1061325.
  13. Peter Damaschke and Azam Sheikh Muhammad. Bounds for nonadaptive group tests to estimate the amount of defectives. In Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part II, pages 117-130, 2010. URL: https://doi.org/10.1007/978-3-642-17461-2_10.
  14. Peter Damaschke and Azam Sheikh Muhammad. Competitive group testing and learning hidden vertex covers with minimum adaptivity. Discrete Math., Alg. and Appl., 2(3):291-312, 2010. URL: https://doi.org/10.1142/S179383091000067X.
  15. R. Dorfman. The detection of defective members of large populations. Ann. Math. Statist., pages 436-440, 1943. Google Scholar
  16. D. Du and F. K Hwang. Combinatorial group testing and its applications. World Scientific Publishing Company., 2000. Google Scholar
  17. D. Du and F. K Hwang. Pooling design and nonadaptive group testing: important tools for dna sequencing. World Scientific Publishing Company., 2006. Google Scholar
  18. Ding-Zhu Du, Frank K. Hwang, Weili Wu, and Taieb Znati. New construction for transversal design. Journal of computational biology : a journal of computational molecular cell biology, 13:990-5, June 2006. URL: https://doi.org/10.1089/cmb.2006.13.990.
  19. Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Estimating the number of defectives with group testing. In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 1376-1380, 2016. URL: https://doi.org/10.1109/ISIT.2016.7541524.
  20. Edwin S. Hong and Richard E. Ladner. Group testing for image compression. IEEE Trans. Image Processing, 11(8):901-911, 2002. URL: https://doi.org/10.1109/TIP.2002.801124.
  21. F. K. Hwang. A method for detecting all defective members in a population by group testing. Journal of the American Statistical Association, 67:605–-608, 1972. Google Scholar
  22. William H. Kautz and Richard C. Singleton. Nonrandom binary superimposed codes. IEEE Trans. Information Theory, 10(4):363-377, 1964. URL: https://doi.org/10.1109/TIT.1964.1053689.
  23. Joseph L.Gastwirth and Patricia A.Hammick. Estimation of the prevalence of a rare disease, preserving the anonymity of the subjects by group testing: application to estimating the prevalence of aids antibodies in blood donors. Journal of Statistical Planning and Inference., 22(1):15-27, 1989. Google Scholar
  24. C. H. Li. A sequential method for screening experimental variables. J. Amer. Statist. Assoc., 57:455-477, 1962. Google Scholar
  25. Anthony J. Macula and Leonard J. Popyack. A group testing method for finding patterns in data. Discrete Applied Mathematics, 144(1-2):149-157, 2004. URL: https://doi.org/10.1016/j.dam.2003.07.009.
  26. Hung Q. Ngo and Ding-Zhu Du. A survey on combinatorial group testing algorithms with applications to DNA library screening. In Discrete Mathematical Problems with Medical Applications, Proceedings of a DIMACS Workshop, December 8-10, 1999, pages 171-182, 1999. URL: https://doi.org/10.1090/dimacs/055/13.
  27. Ely Porat and Amir Rothschild. Explicit nonadaptive combinatorial group testing schemes. IEEE Trans. Information Theory, 57(12):7982-7989, 2011. URL: https://doi.org/10.1109/TIT.2011.2163296.
  28. Dana Ron and Gilad Tsur. The power of an example: Hidden set size approximation using group queries and conditional sampling. CoRR, abs/1404.5568, 2014. URL: http://arxiv.org/abs/1404.5568, URL: http://arxiv.org/abs/1404.5568.
  29. Jens Schlaghoff and Eberhard Triesch. Improved results for competitive group testing. Combinatorics, Probability & Computing, 14(1-2):191-202, 2005. URL: https://doi.org/10.1017/S0963548304006649.
  30. M. Sobel and P. A. Groll. Group testing to eliminate efficiently all defectives in a binomial sample. Bell System Tech. J., 38:1179-1252, 1959. Google Scholar
  31. William H. Swallow. Group testing for estimating infection rates and probabilities of disease transmission. Phytopathology, 1985. Google Scholar
  32. Keith H. Thompson. Estimation of the proportion of vectors in a natural population of insects. Biometrics, 18(4):568-578, 1962. Google Scholar
  33. S. D. Walter, S. W. Hildreth, and B. J. Beaty. Estimation of infection rates in population of organisms using pools of variable size. Am J Epidemiol., 112(1):124-128, 1980. Google Scholar
  34. Jack K. Wolf. Born again group testing: Multiaccess communications. IEEE Trans. Information Theory, 31(2):185-191, 1985. URL: https://doi.org/10.1109/TIT.1985.1057026.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact