TY - JOUR

T1 - On the firefighter problem with spreading vaccination for maximizing the number of saved nodes

T2 - the IP model and LP rounding algorithms

AU - Yang, Yongge

AU - Chen, Po An

AU - Lee, Yu Ching

AU - Fanchiang, Yung Yan

N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Firefighter problem with vaccination spreading

KW - Integer program

KW - Randomized rounding

KW - Vaccination strategy

UR - http://www.scopus.com/inward/record.url?scp=85145222886&partnerID=8YFLogxK

U2 - 10.1007/s11590-022-01963-w

DO - 10.1007/s11590-022-01963-w

M3 - Article

AN - SCOPUS:85145222886

SN - 1862-4472

JO - Optimization Letters

JF - Optimization Letters

ER -