  We consider the influence maximization problem (selecting $k$ seeds in a
network maximizing the expected total influence) on undirected graphs under the
linear threshold model. On the one hand, we prove that the greedy algorithm
always achieves a $(1 - (1 - 1/k)^k + \Omega(1/k^3))$-approximation, showing
that the greedy algorithm does slightly better on undirected graphs than the
generic $(1- (1 - 1/k)^k)$ bound which also applies to directed graphs. On the
other hand, we show that substantial improvement on this bound is impossible by
presenting an example where the greedy algorithm can obtain at most a $(1- (1 -
1/k)^k + O(1/k^{0.2}))$ approximation. This result stands in contrast to the
previous work on the independent cascade model. Like the linear threshold
model, the greedy algorithm obtains a $(1-(1-1/k)^k)$-approximation on directed
graphs in the independent cascade model. However, Khanna and Lucier showed
that, in undirected graphs, the greedy algorithm performs substantially better:
a $(1-(1-1/k)^k + c)$ approximation for constant $c > 0$. Our results show
that, surprisingly, no such improvement occurs in the linear threshold model.
Finally, we show that, under the linear threshold model, the approximation
ratio $(1 - (1 - 1/k)^k)$ is tight if 1) the graph is directed or 2) the
vertices are weighted. In other words, under either of these two settings, the
greedy algorithm cannot achieve a $(1 - (1 - 1/k)^k + f(k))$-approximation for
any positive function $f(k)$. The result in setting 2) is again in a sharp
contrast to Khanna and Lucier's $(1 - (1 - 1/k)^k + c)$-approximation result
for the independent cascade model, where the $(1 - (1 - 1/k)^k + c)$
approximation guarantee can be extended to the setting where vertices are
weighted. We also discuss extensions to more generalized settings including
those with edge-weighted graphs.
