Debashmita Poddar
Séminaire à 10h30
Résumé : The influence maximization (IM) problem is a discrete optimization problem of selecting the k most influential nodes in a network, and has ample applications ranging from viral marketing to outbreak detection. The classic IM problem, which is also referred to as the non-adaptive IM, selects the seed set before starting the diffusion process. In the adaptive setting, selection of the k seed nodes occurs one at a time, such that the j-th seed node is selected after observing the actual influence from the previously selected j − 1 seeds. While adaptive policies are strictly stronger than non-adaptive ones, the latter are much easier to design and implement. A measure called the adaptivity gap (AG), is the ratio between the adaptive and non-adaptive optima. If the AG is small, we say that the non-adaptive policy provides a good approximation of the adaptive optimum. In this seminar, I will present the necessity to bound AG and talk about the techniques that are used to do so.