Abstract
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 (1 - δ) , 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.