Ever since Kempe, Klienberg and Tardos (KKT) published their seminal paper on
maximizing the spread of influence in a social network, there has been
substantial work in this area. In the context of propagations in a social
graph, we can identify three orthogonal dimensions -- the number of seed nodes
activated at the beginning (known as budget), the (expected) number of
activated nodes at the end of the propagation (known as spread or coverage),
and the time taken for the propagation. We can constrain one or two of these
and try to optimize the third. Essentially all the optimization problems are
NP-hard. KKT constrained the budget, left time unconstrained, and optimized the
coverage. In this paper, we revisit their model and propose alternative
optimization problems: MINSEED and MINTIME. In MINSEED, the task is to find the
minimum size seed set such that by activating it, the expected number of nodes
that are eventually activated is larger than some given threshold n. In
MINTIME, in addition to n, a threshold k on the budget is also given, and the
task is to find the seed set of size at most k such that by activating it, >= n
nodes are activated in the expected sense, in the minimum possible time. These
problems generalize the well-known problems of Submodular Set Cover (SSC) and
Robust Asymmetric k-center (RAKC) respectively. We show a greedy algorithm
offers a bicriteria approximation for RSSC, We show this approximation is
tight, in that it cannot be improved. Both results extend to MINSEED. We also
extend known hardness results for RAKC by showing neither bicriteria nor
tricriteria approximations are possible under several conditions. However, when
we allow the budget for number of centers k to be boosted by a logarithmic
factor, then the problem can be solved exactly in PTIME. We extend these
results to MINTIME. All our results also hold for weighted versions of the
problems.