Improved Evolutionary Algorithms for Submodular Maximization with Cost Constraints
<|reference_start|>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 $\mathcal{O}(n^2K_{\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/2$, with probability $1-\epsilon$. The required number of iterations reduces to $\mathcal{O}(nK_{\beta}\log{(1/\epsilon)}/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.<|reference_end|>
@article{zhu2024improved,
    title={Improved Evolutionary Algorithms for Submodular Maximization with Cost
  Constraints},
    author={Yanhui Zhu, Samik Basu, A Pavan},
    journal={Proceedings of the Thirty-Third International Joint Conference on
  Artificial Intelligence (IJCAI-2024)},
    year={2024},
    doi={10.24963/ijcai.2024/783},
    archivePrefix={arXiv},
    eprint={2405.05942},
    primaryClass={cs.DS}
}