  In this paper, we study the problem of minimizing the spread of a viral
epidemic when immunization takes a non-negligible amount of time to take into
effect. Specifically, our problem is to determine which set of nodes to be
vaccinated when vaccines take a random amount of time in order to maximize the
total reward, which is the expected number of saved nodes. We first provide a
mathematical analysis for the reward function of vaccinating an arbitrary
number of nodes when there is a single source of infection. While it is
infeasible to obtain the optimal solution analytically due to the combinatorial
nature of the problem, we establish that the problem is a monotone submodular
maximization problem and develop a greedy algorithm that achieves a
$(1\!-\!1/e)$-approximation. We further extend the scenario to the ones with
multiple infection sources and discuss how the greedy algorithm can be applied
systematically for the multiple-source scenarios. We finally present extensive
simulation results to demonstrate the superiority of our greedy algorithm over
other baseline vaccination strategies.
