Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.8
URN: urn:nbn:de:0030-drops-165422
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16542/
Coja-Oghlan, Amin ; Hahn-Klimroth, Max ; Loick, Philipp ; Penschuck, Manuel
Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study
| pdf-format: |
|
Abstract
The group testing problem asks for efficient pooling schemes and inference algorithms that allow to screen moderately large numbers of samples for rare infections. The goal is to accurately identify the infected individuals while minimizing the number of tests.We propose the novel adaptive pooling scheme adaptive Belief Propagation (ABP) that acknowledges practical limitations such as limited pooling sizes and noisy tests that may give imperfect answers. We demonstrate that the accuracy of ABP surpasses that of individual testing despite using few overall tests. The new design comes with Belief Propagation as an efficient inference algorithm. While the development of ABP is guided by mathematical analyses and asymptotic insights, we conduct an experimental study to obtain results on practical population sizes.
BibTeX - Entry
@InProceedings{cojaoghlan_et_al:LIPIcs.SEA.2022.8,
author = {Coja-Oghlan, Amin and Hahn-Klimroth, Max and Loick, Philipp and Penschuck, Manuel},
title = {{Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study}},
booktitle = {20th International Symposium on Experimental Algorithms (SEA 2022)},
pages = {8:1--8:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-251-8},
ISSN = {1868-8969},
year = {2022},
volume = {233},
editor = {Schulz, Christian and U\c{c}ar, Bora},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16542},
URN = {urn:nbn:de:0030-drops-165422},
doi = {10.4230/LIPIcs.SEA.2022.8},
annote = {Keywords: Group testing, Probabilistic Construction, Belief Propagation, Simulation}
}
| Keywords: | Group testing, Probabilistic Construction, Belief Propagation, Simulation | |
| Seminar: | 20th International Symposium on Experimental Algorithms (SEA 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 11.07.2022 | |
| Supplementary Material: | Software (Source Code): https://github.com/manpen/group-testing |
