Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives
We study the problem of estimating the number of defective items within a pile of elements up to a multiplicative factor of , 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 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 tests. This extends the same lower bound achieved in \cite{ALA17} 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 is achieved by means of non-constructive proof. This improves the lower bound from \cite{ALA17} 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 \emph{expander regular bipartite graphs}, \emph{extractors} and \emph{condensers} to construct two polynomial time algorithms. The first algorithm makes tests, and the second makes tests. This is the first explicit construction with an almost optimal test complexity.