Estimates of for each problem instance.

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 (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.

正如新冠疫情（COVID-19）中所观察到的那样，针对新发大流行病的有效疫苗在初期往往供应有限，必须通过策略性方式进行分配。疫苗分配问题可被建模为一类离散优化问题，已有前期研究表明，即便对其进行近似求解也属于计算难度极高的问题——即NP难（NP-hard）问题。
本文结合理论与实验研究结果，证明该难度瓶颈可被规避。我们的研究结果基于元种群模型（metapopulation model）展开，该模型将整体人口视为由地理上分散的异质性子种群构成，且子种群间存在任意形式的迁徙模式。在此模型框架下，疫苗组合按子种群层级进行分配，因此疫苗分配问题可被转化为在预算约束下最大化整数格函数（integer lattice function）的优化问题。
本文针对该问题考量了多款经典简易的贪心算法（greedy algorithms），并通过三个不同规模的问题实例验证了这些算法的有效性：新罕布什尔州（10个郡，总人口140万）、艾奥瓦州（99个郡，总人口320万）以及得克萨斯州（254个郡，总人口3003万）。
针对该算法有效性，本文给出了理论解释：我们证明了这些算法的近似因子（approximation factor，即衡量算法针对某问题实例的输出与理论最优解之间差距的指标）取决于目标函数（objective function）g的子模率（submodularity ratio）。函数的子模率用于衡量目标函数g与子模函数的偏离程度；此处的子模性（submodularity）指集合函数与格函数所具备的极具实用价值的“边际效益递减”（diminishing returns）特性，即当函数输入增加时，函数值虽会上升，但增幅会逐步收窄的性质。