Keithley Jeffrey, Choudhuri Akash, Adhikari Bijaya, Pemmaraju Sriram V
Department of Computer Science, University of Iowa, Iowa City, Iowa, United States of America.
PLoS Comput Biol. 2025 Jul 21;21(7):e1012539. doi: 10.1371/journal.pcbi.1012539. eCollection 2025 Jul.
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.
正如在新冠疫情的案例中所观察到的那样，针对新出现的大流行的有效疫苗最初往往供应有限，必须进行战略分配。疫苗分配可以建模为一个离散优化问题，先前的研究表明，即使是近似求解这个问题在计算上也很困难（即NP难问题）。通过结合理论和实验结果，我们表明可以规避这种困难结果。我们在一个元种群模型的背景下展示我们的结果，该模型将一个种群视为由地理上分散的异质子种群组成，它们之间具有任意的流动模式。在这种情况下，疫苗包在子种群层面进行分配，因此疫苗分配问题可以表述为在预算约束[公式：见原文]下最大化一个整数格函数[公式：见原文]的问题。我们考虑了针对这个问题的各种简单且著名的贪心算法，并展示了这些算法在不同规模的三个问题实例上的有效性：新罕布什尔州（10个县，人口140万）、爱荷华州（99个县，人口320万）和德克萨斯州（254个县，人口3003万）。我们通过表明这些算法的近似因子（衡量问题实例的算法输出与其理论最优值的比较程度）取决于目标函数g的次模性比率，为这种有效性提供了理论解释。函数的次模性比率衡量g与次模性的距离；这里的次模性指的是集合和格函数非常有用的“收益递减”性质，即随着函数输入增加，函数值增加，但增加的幅度不大。
