2023/06/27 by Bshouty, Nader H., Haddad-Zaknoon, Catherine A.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2307.04822
Group testing is an approach aimed at identifying up to d defective items among a total of n elements. This is accomplished by examining subsets to determine if at least one defective item is present. In our study, we focus on the problem of identifying a subset of ℓ≤ d defective items. We develop upper and lower bounds on the number of tests required to detect ℓ defective items in both the adaptive and non-adaptive settings while considering scenarios where no prior knowledge of d is available, and situations where an estimate of d or at least some non-trivial upper bound on d is available. When no prior knowledge on d is available, we prove a lower bound of Ω((ℓ log2n)/(log ℓ +loglog n)) tests in the randomized non-adaptive settings and an upper bound of O(ℓ log2 n) for the same settings. Furthermore, we demonstrate that any non-adaptive deterministic algorithm must ask Θ(n) tests, signifying a fundamental limitation in this scenario. For adaptive algorithms, we establish tight bounds in different scenarios. In the deterministic case, we prove a tight bound of Θ(ℓlog(n/ℓ)). Moreover, in the randomized settings, we derive a tight bound of Θ(ℓlog(n/d)). When d, or at least some non-trivial estimate of d, is known, we prove a tight bound of Θ(dlog (n/d)) for the deterministic non-adaptive settings, and Θ(ℓlog(n/d)) for the randomized non-adaptive settings. In the adaptive case, we present an upper bound of O(ℓ log (n/ℓ)) for the deterministic settings, and a lower bound of Ω(ℓlog(n/d)+log n). Additionally, we establish a tight bound of Θ(ℓ log(n/d)) for the randomized adaptive settings.