Metapopulation model notation.

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）的框架下展示研究成果：该模型将整体种群视为由地理上分散的异质性亚种群构成，且亚种群间存在任意模式的人口流动。在此设定下，疫苗组合按亚种群层面进行分配，因此疫苗分配问题可被建模为在预算约束（budget constraint）下最大化整数格函数（integer lattice function）的问题。我们针对该问题设计了多种经典简单贪心算法，并在三个不同规模的实例中验证了算法的有效性：新罕布什尔州（10个县，总人口140万）、艾奥瓦州（99个县，总人口320万）以及得克萨斯州（254个县，总人口3003万）。我们针对该有效性给出了理论解释：证明这些算法的近似因子（即衡量算法输出结果与问题理论最优解差距的指标）取决于目标函数g的次模性比率（submodularity ratio）。函数的次模性比率用于衡量目标函数g与次模函数（submodularity）的偏离程度；此处次模性指集合函数与格函数所具备的极具实用价值的“收益递减”特性，即当函数输入增大时，函数值虽会上升，但增幅逐渐收窄。