文章基本信息

标题：Lower Bound for Non-Adaptive Estimation of the Number of Defective Items
本地全文：下载
作者：Nader H. Bshouty
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：149
页码：1-9
DOI：10.4230/LIPIcs.ISAAC.2019.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that to estimate within a constant factor the number of defective items in a non-adaptive randomized group testing algorithm we need at least Omega~(log n) tests. This solves the open problem posed by Damaschke and Sheikh Muhammad in [Peter Damaschke and Azam Sheikh Muhammad, 2010; Peter Damaschke and Azam Sheikh Muhammad, 2010].
关键词：Group Testing; Estimation; Defective Items