Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives

Nader H. Bshouty, Catherine A. Haddad-Zaknoon

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We study the problem of estimating the number of defective items d within a pile of n elements up to a multiplicative factor of Δ> 1, using deterministic group testing algorithms. We bring lower and upper bounds on the number of tests required in both the adaptive and the non-adaptive deterministic settings given an upper bound D on the defectives number. For the adaptive deterministic settings, our results show that, any algorithm for estimating the defectives number up to a multiplicative factor of Δ must make at least Ω((D/ Δ2) log (n/ D) ) tests. This extends the same lower bound achieved in [1] for non-adaptive algorithms. Moreover, we give a polynomial time adaptive algorithm that shows that our bound is tight up to a small additive term. For non-adaptive algorithms, an upper bound of O((D/ Δ2) (log (n/ D) + log Δ) ) is achieved by means of non-constructive proof. This improves the lower bound Ω((log D) / (log Δ) ) Dlog n) from [1] and matches the lower bound up to a small additive term. In addition, we study polynomial time constructive algorithms. We use existing polynomial time constructible expander regular bipartite graphs, extractors and condensers to construct two polynomial time algorithms. The first algorithm makes O((D1+o(1)/ Δ2) · log n) tests, and the second makes (D/ Δ2) · Quazipoly (log n) tests. This is the first explicit construction with an almost optimal test complexity.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفCombinatorial Optimization and Applications - 14th International Conference, COCOA 2020, Proceedings
المحررونWeili Wu, Zhongnan Zhang
ناشرSpringer Science and Business Media Deutschland GmbH
الصفحات393-410
عدد الصفحات18
رقم المعيار الدولي للكتب (المطبوع)9783030648428
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2020
الحدث14th International Conference on Combinatorial Optimization and Applications, COCOA 2020 - Dallas, الولايات المتّحدة
المدة: ١١ ديسمبر ٢٠٢٠١٣ ديسمبر ٢٠٢٠

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت12577 LNCS

!!Conference

!!Conference14th International Conference on Combinatorial Optimization and Applications, COCOA 2020
الدولة/الإقليمالولايات المتّحدة
المدينةDallas
المدة١١/١٢/٢٠١٣/١٢/٢٠

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا