  In the adaptive influence maximization problem, we are given a social network
and a budget $k$, and we iteratively select $k$ nodes, called seeds, in order
to maximize the expected number of nodes that are reached by an influence
cascade that they generate according to a stochastic model for influence
diffusion. Differently from the non-adaptive influence maximization problem,
where all the seeds must be selected beforehand, here nodes are selected
sequentially one by one, and the decision on the $i$th seed is based on the
observed cascade produced by the first $i-1$ seeds. We focus on the myopic
feedback model, in which we can only observe which neighbors of previously
selected seeds have been influenced and on the independent cascade model, where
each edge is associated with an independent probability of diffusing influence.
Previous works showed that the adaptivity gap is at most $4$, which implies
that the non-adaptive greedy algorithm guarantees an approximation factor of
$\frac{1}{4}\left(1-\frac{1}{e}\right)$ for the adaptive problem. In this
paper, we improve the bounds on both the adaptivity gap and on the
approximation factor. We directly analyze the approximation factor of the
non-adaptive greedy algorithm, without passing through the adaptivity gap, and
show that it is at least $\frac{1}{2}\left(1-\frac{1}{e}\right)$. Therefore,
the adaptivity gap is at most $\frac{2e}{e-1}\approx 3.164$. To prove these
bounds, we introduce a new approach to relate the greedy non-adaptive algorithm
to the adaptive optimum. The new approach does not rely on multi-linear
extensions or random walks on optimal decision trees, which are commonly used
techniques in the field. We believe that it is of independent interest and may
be used to analyze other adaptive optimization problems.
