Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints

We present an evolutionary algorithm evo-SMC for the problem of Submodular Maximization under Cost constraints (SMC). Our algorithm achieves $1\mathrm{/}2$-approximation with a high probability $1-1\mathrm{/}n$ within $\mathcal{O}(n^2{K}_{\beta })$ iterations, where $K_{\beta }$ denotes the maximum size of a feasible solution set with cost constraint $\beta$. To the best of our knowledge, this is the best approximation guarantee offered by evolutionary algorithms for this problem. We further refine evo-SMC, and develop st-evo-SMC. This stochastic version yields a significantly faster algorithm while maintaining the approximation ratio of $1\mathrm{/}2$, with probability $1-\epsilon$. The required number of iterations reduces to $\mathcal{O}(n{K}_{\beta }\log (1\mathrm{/}\epsilon )\mathrm{/}p)$, where the user defined parameters $p\in (0,1]$ represents the stochasticity probability, and $\epsilon \in (0,1]$ denotes the error threshold. Finally, the empirical evaluations carried out through extensive experimentation substantiate the efficiency and effectiveness of our proposed algorithms. Our algorithms consistently outperform existing methods, producing higher-quality solutions.