  In this paper, the Minimum Cost Submodular Cover problem is studied, which is
to minimize a modular cost function such that the monotone submodular benefit
function is above a threshold. For this problem, an evolutionary algorithm EASC
is introduced that achieves a constant, bicriteria approximation in expected
polynomial time; this is the first polynomial-time evolutionary approximation
algorithm for Minimum Cost Submodular Cover. To achieve this running time,
ideas motivated by submodularity and monotonicity are incorporated into the
evolutionary process, which likely will extend to other submodular optimization
problems. In a practical application, EASC is demonstrated to outperform the
greedy algorithm and converge faster than competing evolutionary algorithms for
this problem.
