Journal article
Analyzing greedy vaccine allocation algorithms for metapopulation disease models
PLoS computational biology, Vol.21(7), e1012539
07/21/2025
DOI: 10.1371/journal.pcbi.1012539
PMCID: PMC12289052
PMID: 40690489
Abstract
As observed in the case of COVID-19, effective vaccines for an emerging pandemic tend to be in limited supply initially and must be allocated strategically. The allocation of vaccines can be modeled as a discrete optimization problem that prior research has shown to be computationally difficult (i.e., NP-hard) to solve even approximately. Using a combination of theoretical and experimental results, we show that this hardness result may be circumvented. We present our results in the context of a metapopulation model, which views a population as composed of geographically dispersed heterogeneous subpopulations, with arbitrary travel patterns between them. In this setting, vaccine bundles are allocated at a subpopulation level, and so the vaccine allocation problem can be formulated as a problem of maximizing an integer lattice function [Formula: see text] subject to a budget constraint [Formula: see text]. We consider a variety of simple, well-known greedy algorithms for this problem and show the effectiveness of these algorithms for three problem instances at different scales: New Hampshire (10 counties, population 1.4 million), Iowa (99 counties, population 3.2 million), and Texas (254 counties, population 30.03 million). We provide a theoretical explanation for this effectiveness by showing that the approximation factor (a measure of how well the algorithmic output for a problem instance compares to its theoretical optimum) of these algorithms depends on the submodularity ratio of the objective function g. The submodularity ratio of a function is a measure of how distant g is from being submodular; here submodularity refers to the very useful "diminishing returns" property of set and lattice functions, i.e., the property that as the function inputs are increased the function value increases, but not by as much.
Details
- Title: Subtitle
- Analyzing greedy vaccine allocation algorithms for metapopulation disease models
- Creators
- Jeffrey Keithley - University of IowaAkash Choudhuri - University of IowaBijaya Adhikari - University of IowaSriram V Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- PLoS computational biology, Vol.21(7), e1012539
- DOI
- 10.1371/journal.pcbi.1012539
- PMID
- 40690489
- PMCID
- PMC12289052
- NLM abbreviation
- PLoS Comput Biol
- ISSN
- 1553-7358
- eISSN
- 1553-7358
- Publisher
- PUBLIC LIBRARY SCIENCE
- Grant note
- Centers for Disease Control and Prevention: U01CK000594 NSF: 1955939
Funding for this research was provided as part of the CDC MInD Healthcare group under cooperative agreement U01CK000594 and associated Covid19 supplemental funding. Authors BA and SVP were awarded the grant and all 4 authors were supported by the grant https://www.cdc.gov/hai/research/MIND-Healthcare.html. Additional funding was provided by NSF Award Number 1955939. Author SVP was awarded this grant and authors JK and SVP were supported by the grant. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
- Language
- English
- Date published
- 07/21/2025
- Academic Unit
- Computer Science
- Record Identifier
- 9984865316002771
Metrics
3 Record Views