Paper Info
Title
Scalable and Memory-Efficient Algorithms for Controlling Networked Epidemic Processes Using Multiplicative Weights Update Method.
Abstract
We study the problem of designing scalable algorithms to find effective intervention strategies for controlling stochastic epidemic processes on networks. This is a common problem arising in agent based models for epidemic spread. Previous approaches to this problem focus on either heuristics with no guarantees or approximation algorithms that scale only to networks corresponding to county-sized populations, typically, with less than a million nodes. In particular, the mathematical-programming based approaches need to solve the Linear Program (LP) relaxation of the problem using an LP solver, which restricts the scalability of this approach. In this work, we overcome this restriction by designing an algorithm that adapts the multiplicative weights update (MWU) framework, along with the sample average approximation (SAA) technique, to approximately solve the linear program (LP) relaxation for the problem. To scale this approach further, we provide a memory-efficient algorithm that enables scaling to large networks, corresponding to country-size populations, with over 300 million nodes and 30 billion edges. Furthermore, we show that this approach provides near-optimal solutions to the LP in practice.
Year
DOI
Venue
2022
10.24963/ijcai.2022/717
International Joint Conference on Artificial Intelligence
Keywords
DocType
Citations 
Agent-based and Multi-agent Systems: Resource Allocation,AI Ethics, Trust, Fairness: Fairness & Diversity,Data Mining: Networks,Multidisciplinary Topics and Applications: Health and Medicine
Conference
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Prathyush Sambaturu111.30
Marco Minutoli2189.22
Mahantesh Halappanavar321833.64
Kalyanaraman, Ananth422131.95
Anil Kumar S. Vullikanti5113598.30