Proof of Theorem 4.1.

<div> Determining COVID-19 vaccination strategies presents many challenges in light of limited vaccination capacity and the heterogeneity of affected communities. Who should be prioritized for early vaccination when different groups manifest different levels of risks and contact rates? Answering such questions often becomes computationally intractable given that network size can exceed millions. We obtain a framework to compute the optimal vaccination strategy within seconds to minutes from among all strategies, including highly dynamic ones that adjust vaccine allocation as often as required, and even with modest computation resources. We then determine the optimal strategy for a large range of parameter values representative of various US states, countries, and case studies including retirement homes and prisons. The optimal is almost always one of a few candidate strategies, and, even when not, the suboptimality of the best among these candidates is minimal. Further, we find that many commonly deployed vaccination strategies, such as vaccinating the high risk group first, or administering second doses without delay, can often incur higher death rates, hospitalizations, and symptomatic infection counts. Our framework can be easily adapted to future variants or pandemics through appropriate choice of the compartments of the disease and parameters. </div>