Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions

In this paper, the monotone submodular maximization problem (SM) is studied. SM is to find a subset of size $κ$ 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-ε)(1-1/e)$ in expectation for every cardinality constraint $κ< P$, where $P\leq n+1$ is an input, in $O(nP\ln(1/ε))$ 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-ε)(1-1/e)$ in expectation for every cardinality constraint $κ< P$ in $O(n\ln(P)\ln(1/ε))$ queries of $f$. Further, the biased Pareto optimization algorithm can be modified in order to achieve a worst-case ratio of $(1-ε)(1-1/e)$ in expectation for cardinality constraint $κ$ in $O(n\ln(1/ε))$ 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.