When an infectious disease spreads, how to quickly vaccinate with a limited budget per time step to reduce the impact of the virus is very important. Specifically, vaccination will be carried out in every time step, and vaccinated nodes will no longer be infected. Meanwhile, the protection from vaccination can spread to the neighbors of a vaccinated node. Our goal is to efficiently find optimal and approximation solutions to our problem with various algorithms. In this paper, we first design an integer linear program to solve this problem. We then propose approximation algorithms of (1) Linear programming (LP) deterministic threshold rounding, (2) LP dependent randomized rounding, and (3) LP independent randomized rounding. We prove that the LP independent randomized rounding algorithm has a high probability of finding a feasible solution that gives an approximation ratio of , where a small constant between 0 and 1 reduces the lower bound on the feasibility probability. We also provide experimental results for three different rounding algorithms to show that they perform numerically well in terms of approximation ratios. These analytical and numerical studies allow each individual to adopt the most appropriate approximation algorithm to efficiently resolve the vaccination problem when her reliance on commercial optimization solvers is costly.
Keywords: Firefighter problem with vaccination spreading; Integer program; Randomized rounding; Vaccination strategy.
© The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2022, Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.