  We study the problem of revenue maximization in the marketing model for
social networks introduced by (Hartline, Mirrokni, Sundararajan, WWW '08). We
restrict our attention to the Uniform Additive Model and mostly focus on
Influence-and-Exploit (IE) marketing strategies. We obtain a comprehensive
collection of results on the efficiency and the approximability of IE
strategies, which also imply a significant improvement on the best known
approximation ratios for revenue maximization. Specifically, we show that in
the Uniform Additive Model, both computing the optimal marketing strategy and
computing the best IE strategy are $\NP$-hard for undirected social networks.
We observe that allowing IE strategies to offer prices smaller than the myopic
price in the exploit step leads to a measurable improvement on their
performance. Thus, we show that the best IE strategy approximates the maximum
revenue within a factor of 0.911 for undirected and of roughly 0.553 for
directed networks. Moreover, we present a natural generalization of IE
strategies, with more than two pricing classes, and show that they approximate
the maximum revenue within a factor of roughly 0.7 for undirected and of
roughly 0.35 for directed networks. Utilizing a connection between good IE
strategies and large cuts in the underlying social network, we obtain
polynomial-time algorithms that approximate the revenue of the best IE strategy
within a factor of roughly 0.9. Hence, we significantly improve on the best
known approximation ratio for revenue maximization to 0.8229 for undirected and
to 0.5011 for directed networks (from 2/3 and 1/3, respectively, by Hartline et
al.).
