Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.2
URN: urn:nbn:de:0030-drops-114983
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11498/
Bshouty, Nader H.
Lower Bound for Non-Adaptive Estimation of the Number of Defective Items
| pdf-format: |
|
Abstract
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].
BibTeX - Entry
@InProceedings{bshouty:LIPIcs:2019:11498,
author = {Nader H. Bshouty},
title = {{Lower Bound for Non-Adaptive Estimation of the Number of Defective Items}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {2:1--2:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11498},
URN = {urn:nbn:de:0030-drops-114983},
doi = {10.4230/LIPIcs.ISAAC.2019.2},
annote = {Keywords: Group Testing, Estimation, Defective Items}
}
| Keywords: | Group Testing, Estimation, Defective Items | |
| Seminar: | 30th International Symposium on Algorithms and Computation (ISAAC 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 28.11.2019 |
