Join our colleague Aravind Srinivasan, University of Maryland, for his talk "Controlling Epidemic Spread through Stochastic Networks."
The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinInf problem involves minimizing the expected number of infections when the disease starts at a designated vertex and we are allowed to break at most $B$ edges (or at most $B$ vertices, in the case of vaccination) of the graph. This type of intervention naturally corresponds to implementing social distancing (or vaccination, respectively), and as the COVID-19 pandemic has shown, it is critical in mitigating the infection spread. Although this problem is fundamental in epidemiology, it has remained generally open. In this paper, we study the MinInf problem under the Chung-Lu random graph model, and develop a Sample Average Approximation (SAA) scheme for it. We further show that for certain parameters of the random-graph model affecting the number of paths in a randomly-drawn graph, our framework yields rigorous bicriteria approximation algorithms. Finally, we complement the latter by providing cases demonstrating the limits of our SAA approach.

This is joint work with Michael Dinitz (Johns Hopkins University), Leonidas Tsepenekas (University of Maryland), and Anil Vullikanti (University of Virginia).
12 August 2021

свернуть