  We consider the subset selection problem for function $f$ with constraint
bound $B$ that changes over time. Within the area of submodular optimization,
various greedy approaches are commonly used. For dynamic environments we
observe that the adaptive variants of these greedy approaches are not able to
maintain their approximation quality. Investigating the recently introduced
POMC Pareto optimization approach, we show that this algorithm efficiently
computes a $\phi= (\alpha_f/2)(1-\frac{1}{e^{\alpha_f}})$-approximation, where
$\alpha_f$ is the submodularity ratio of $f$, for each possible constraint
bound $b \leq B$. Furthermore, we show that POMC is able to adapt its set of
solutions quickly in the case that $B$ increases. Our experimental
investigations for the influence maximization in social networks show the
advantage of POMC over generalized greedy algorithms. We also consider EAMC, a
new evolutionary algorithm with polynomial expected time guarantee to maintain
$\phi$ approximation ratio, and NSGA-II with two different population sizes as
advanced multi-objective optimization algorithm, to demonstrate their
challenges in optimizing the maximum coverage problem. Our empirical analysis
shows that, within the same number of evaluations, POMC is able to perform as
good as NSGA-II under linear constraint, while EAMC performs significantly
worse than all considered algorithms in most cases.
