Abstract
We studied the problem of designing intervention strategies (e.g. vaccinations), under budget constraints, to minimize the spread of an epidemic outbreak. This is a challenging stochastic optimization problem in the context of the SIR epidemic model on a network. Previous approaches for this problem were either heuristics or approximation algorithms for restricted settings (e.g., transmission probability p = 1). We developed a bicriteria approximation algorithm, called SaaRound, for the EpiControl problem, using techniques from stochastic optimization. Our algorithm provides empirical guarantees for solution quality in graphs of moderate size. We empirically evaluated our approach on various networks such as synthetic agent-based populations, random, and real-world collaboration networks. Our algorithm outperformed standard baseline heuristics (e.g., remove nodes with a high degree). Also, we showed that our approach obtained near-optimal interventions in practice.
The main bottleneck of the SaaRound algorithm is using a solver to obtain a fractional optimal solution for the LP relaxation of the EpiControl problem. To overcome this bottleneck, we developed an approximation algorithm, adapting the Multiplicative Weights Update (MWU) method and the SAA technique, such that it bypasses the need to use a solver, to approximately solve the LP. We provided a memory-efficient version of this algorithm to scale this approach further, which allowed scaling to very large networks corresponding to state- and country-level populations.
Further, we considered a version of the EpiControl problem, where the sources might not be known precisely. In such a setting, a min-max objective, where the goal is to minimize the maximum expected outbreak size in any possible scenario, gives a more robust solution compared to the interventions considered for a single scenario. We developed rigorous approximation algorithms for this problem and evaluated its performance on different random graphs.
Finally, we considered the problem of extending our approach to control problems in other epidemic models that follow SIR class dynamics (e.g., SEI, SI). To this end, we developed a simple framework to extend our approach to such models. Particularly, we focused on the problem of designing group-scale interventions, to control the spread of invasive alien species (IAS), that affect crops, across a landscape. Our goal was to find a set of regions to intervene, satisfying budget constraints, such that the spread of IAS is minimized. We developed a bicriteria approximation algorithm for finding effective group-scale interventions for this problem and showed its performance guarantees. Further, we evaluated our algorithm on real-world networks and compared it with standard baselines.
