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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2020
אירוע14th International Conference on Combinatorial Optimization and Applications, COCOA 2020 - Dallas, ארצות הברית
משך הזמן: 11 דצמ׳ 202013 דצמ׳ 2020

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך12577 LNCS

כנס

כנס14th International Conference on Combinatorial Optimization and Applications, COCOA 2020
מדינה/אזורארצות הברית
עירDallas
תקופה11/12/2013/12/20

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי