License: Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16542/
Go to the corresponding LIPIcs Volume Portal

Coja-Oghlan, Amin ; Hahn-Klimroth, Max ; Loick, Philipp ; Penschuck, Manuel

Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study

pdf-format:
LIPIcs-SEA-2022-8.pdf (1 MB)

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
Collection: 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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI