Optimizing Pool Testing for Epidemic Surveillance

Testing is one of the key tools in public health surveillance. Often testing resources are limited, and pooled testing emerged as a viable strategy during the COVID outbreak, for early detection of the outbreak or clearing the most number of individuals (maximum “welfare”). Here, we study the problem of selecting pools for testing which maximizes welfare. However, this problem is a very challenging optimization problem because the infection status of individuals can be correlated. Prior work on choosing pools has ignored network correlations. We design an efficient approximation algorithm for this problem, using techniques from stochastic and combinatorial optimization: sample average approximation, linear programming and randomizedrounding. Wefurtherspeedupouralgorithmsusingtechniques for combinatorially solving the linear program. We evaluate our method on multiple networked datasets, including one derived from a hospital, and show significant benefit in modeling network correlations.

Authors

• Jack Heavey University of Virginia
• Abhijin Adiga University of Virginia
• Anil Vullikanti University of Virginia

Keywords

• Networks
• optimization
• approximation algorithms
• SOPS