GPCE Seminar Series
Date/time: Thursday, August 12, 11:30am – 12:30pm Eastern (USA)
Topic: Controlling Epidemic Spread through Stochastic Networks
Speaker: Aravind Srinivasan
Zoom link: https://virginia.zoom.us/j/92700002677?pwd=Zi8vQ21TUHpBQVYxQXFpaTZPY2FNdz09
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).
Aravind Srinivasan is a Distinguished University Professor and Professor of Computer Science, UMIACS, and AMSC, at the University of Maryland, College Park. His main research interests are in algorithms, probabilistic methods, data science, network science, and machine learning theory and applications in areas including health, E-commerce, cloud computing, internet advertising, and fairness. They span areas including: algorithms, probabilistic methods, and continuous/combinatorial optimization; the interface of algorithms, AI, and machine learning in data science and health including computational epidemiology, cancer genomics, pharmacology, organ exchange, and medical devices; data science and the internet economy including E-commerce, digital marketing, cloud optimization, crowdsourcing, and social networks; data science and fairness, systematically incorporating (probabilistic, per user/demographic) fairness in AI and in algorithms; algorithms in networking, social networks, and distributed/parallel computing; and computational approaches to sustainable growth (including energy, monitoring and sensing, electric-power and water networks).