Publication date: Oct 12, 2024
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 subject to a budget constraint. 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 of these algorithms depends on the submodularity ratio of objective function g, a measure of how distant g is from being submodular.
Semantics
| Type | Source | Name |
|---|---|---|
| disease | MESH | COVID-19 |
| disease | MESH | infections |
| disease | IDO | algorithm |
| disease | IDO | infection |
| disease | IDO | infectivity |
| disease | IDO | infection incidence |
| drug | DRUGBANK | Methionine |