Engineering Papers⌕ Search

Engineering topics

Sambaturu, Prathyush

Publications and source records attributed to Sambaturu, Prathyush.

Scalable and Memory-Efficient Algorithms for Controlling Networked Epidemic Processes Using Multiplicative Weights Update Method

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.

Sambaturu, Prathyush↗

PREEMPT: Scalable Epidemic Interventions Using Submodular Optimization on Multi-GPU Systems

Preventing and slowing the spread of epidemics is achieved through techniques such as vaccination and social distancing. Given practical limitations on the number of vaccines and cost of administration, optimization becomes a necessity. Previous approaches using mathematical programming methods have shown to be effective but are limited by computational costs. In this work, we make several contributions: First, we present a new approach for intervention via maximizing the influence of vaccinated nodes on the network. We call this method \preempt. Next, we prove submodular properties associated with the objective function of our method so that it aids in construction of an efficient greedy approximation strategy. Consequently, we present a new parallel algorithm based on greedy hill climbing for \preempt, and present an efficient parallel implementation for distributed CPU-GPU heterogeneous platforms. Our results demonstrate that \preempt{} is able to achieve a significant reduction (up to 6.75$\times$) in the percentage of people infected on a city-scale network. We also show strong scaling results of \preempt{} on 128 nodes of the Summit supercomputer. Our parallel implementation is able to significantly reduce time to solution, from hours to minutes on large networks. This work represents a first-of-its-kind effort in parallelizing greedy hill climbing and applying it toward devising effective interventions for epidemics.

Minutoli, Marco↗