Crackovid: Optimizing Group Testing
This work addresses the challenge of efficient COVID-19 testing for public health, though it appears incremental as it builds on existing group testing frameworks with new optimization approaches.
The paper tackles the problem of optimizing group testing for COVID-19 by developing strategies to minimize the number of tests while maximizing information, using Bayesian priors for infections and test errors. It proposes a mathematically principled objective based on information theory, optimizes non-adaptive strategies with genetic algorithms, and provides theoretical guarantees for adaptive methods using adaptive sub-modularity.
We study the problem usually referred to as group testing in the context of COVID-19. Given $n$ samples taken from patients, how should we select mixtures of samples to be tested, so as to maximize information and minimize the number of tests? We consider both adaptive and non-adaptive strategies, and take a Bayesian approach with a prior both for infection of patients and test errors. We start by proposing a mathematically principled objective, grounded in information theory. We then optimize non-adaptive optimization strategies using genetic algorithms, and leverage the mathematical framework of adaptive sub-modularity to obtain theoretical guarantees for the greedy-adaptive method.