  In this paper, the monotone submodular maximization problem (SM) is studied.
SM is to find a subset of size $\kappa$ from a universe of size $n$ that
maximizes a monotone submodular objective function $f$.
  We show using a novel analysis that the Pareto optimization algorithm
achieves a worst-case ratio of $(1-\epsilon)(1-1/e)$ in expectation for every
cardinality constraint $\kappa < P$, where $P\leq n+1$ is an input, in
$O(nP\ln(1/\epsilon))$ queries of $f$.
  In addition, a novel evolutionary algorithm called the biased Pareto
optimization algorithm, is proposed that achieves a worst-case ratio of
$(1-\epsilon)(1-1/e)$ in expectation for every cardinality constraint $\kappa <
P$ in $O(n\ln(P)\ln(1/\epsilon))$ queries of $f$. Further, the biased Pareto
optimization algorithm can be modified in order to achieve a worst-case ratio
of $(1-\epsilon)(1-1/e)$ in expectation for cardinality constraint $\kappa$ in
$O(n\ln(1/\epsilon))$ queries of $f$.
  An empirical evaluation corroborates our theoretical analysis of the
algorithms, as the algorithms exceed the stochastic greedy solution value at
roughly when one would expect based upon our analysis.
