Designing Robust Interventions to Control Epidemic Outbreaks

摘要

We study the problem of controlling the spread of an epidemic outbreak on a network by deploying vaccines. Typically, the supply of vaccines is limited, and becomes available over time. Therefore, vaccination decisions have to be made in multiple stages. These are challenging optimization problems when the networks are arbitrary. Further, many components of the epidemic model, e.g., the source of the outbreak might not be known, and parameters might be not known precisely. In such a setting, a min-max objective, which minimizes the maximum outbreak size in any scenario (which corresponds to specific source or parameter setting), gives a more robust solution, than tailoring the intervention to a single scenario. In this paper, we develop rigorous approximation algorithms for vaccine allocation in single and two-stages, for the min-max objective. We evaluate our algorithms on different random graph models. We find that the nodes picked in the interventions at different stages have very different characteristics. We also find that solutions optimized for a single scenario can be significantly sub-optimal with respect to the min-max objective.