Controlling Epidemic Spread Through Stochastic Networks
Speaker: Aravind Srinivasan, Distinguished University Professor and Professor of Computer Science, UMIACS, and AMSC, at the University of Maryland, College Park
Abstract: The spread of an epidemic is often modeled by a 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).