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/2$-approximation with a high probability $1-1/n$ within O(n²Kβ) iterations, where Kβ denotes the maximum size of a feasible solution set with cost constraint β. 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/2$, with probability 1-ε. The required number of iterations reduces to O(nKβlog(1/ε)/p), where the user defined parameters p ∈ (0,1] represents the stochasticity probability, and ε ∈ (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.