Improved Dynamic Algorithm for Non-monotone Submodular Maximization under Cardinality Constraint

Kiarash Banihashem, Samira Goudarzi, Mohammadtaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:6298-6308, 2026.

Abstract

We study fully dynamic non-monotone submodular maximization under a cardinality constraint $k$. Prior work achieved approximation guarantees of $(0.125-\epsilon)$ using $\tilde{O}(\epsilon^{-1}k^2)$ oracle queries per update (NeurIPS’20) and $0.171$ using $\tilde{O}(\epsilon^{-3}k^4)$ oracle queries per update (NeurIPS’25). In this work, we present a dynamic algorithm that achieves a $0.262$-approximation with worst-case expected update time $O(\epsilon^{-3}k\log(k)\log(\epsilon^{-1}k) + \epsilon^{-2}k^2\log(k))$, where $0 < \epsilon \leq 1$ is the error parameter. We also develop another dynamic algorithm with update time bounded by $\mathrm{poly}(\epsilon^{-1},k)$ that achieves a $0.277$-approximation guarantee.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-banihashem26c, title = {Improved Dynamic Algorithm for Non-monotone Submodular Maximization under Cardinality Constraint}, author = {Banihashem, Kiarash and Goudarzi, Samira and Hajiaghayi, Mohammadtaghi and Jabbarzade, Peyman and Monemizadeh, Morteza}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {6298--6308}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/banihashem26c/banihashem26c.pdf}, url = {https://proceedings.mlr.press/v306/banihashem26c.html}, abstract = {We study fully dynamic non-monotone submodular maximization under a cardinality constraint $k$. Prior work achieved approximation guarantees of $(0.125-\epsilon)$ using $\tilde{O}(\epsilon^{-1}k^2)$ oracle queries per update (NeurIPS’20) and $0.171$ using $\tilde{O}(\epsilon^{-3}k^4)$ oracle queries per update (NeurIPS’25). In this work, we present a dynamic algorithm that achieves a $0.262$-approximation with worst-case expected update time $O(\epsilon^{-3}k\log(k)\log(\epsilon^{-1}k) + \epsilon^{-2}k^2\log(k))$, where $0 < \epsilon \leq 1$ is the error parameter. We also develop another dynamic algorithm with update time bounded by $\mathrm{poly}(\epsilon^{-1},k)$ that achieves a $0.277$-approximation guarantee.} }
Endnote
%0 Conference Paper %T Improved Dynamic Algorithm for Non-monotone Submodular Maximization under Cardinality Constraint %A Kiarash Banihashem %A Samira Goudarzi %A Mohammadtaghi Hajiaghayi %A Peyman Jabbarzade %A Morteza Monemizadeh %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-banihashem26c %I PMLR %P 6298--6308 %U https://proceedings.mlr.press/v306/banihashem26c.html %V 306 %X We study fully dynamic non-monotone submodular maximization under a cardinality constraint $k$. Prior work achieved approximation guarantees of $(0.125-\epsilon)$ using $\tilde{O}(\epsilon^{-1}k^2)$ oracle queries per update (NeurIPS’20) and $0.171$ using $\tilde{O}(\epsilon^{-3}k^4)$ oracle queries per update (NeurIPS’25). In this work, we present a dynamic algorithm that achieves a $0.262$-approximation with worst-case expected update time $O(\epsilon^{-3}k\log(k)\log(\epsilon^{-1}k) + \epsilon^{-2}k^2\log(k))$, where $0 < \epsilon \leq 1$ is the error parameter. We also develop another dynamic algorithm with update time bounded by $\mathrm{poly}(\epsilon^{-1},k)$ that achieves a $0.277$-approximation guarantee.
APA
Banihashem, K., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P. & Monemizadeh, M.. (2026). Improved Dynamic Algorithm for Non-monotone Submodular Maximization under Cardinality Constraint. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:6298-6308 Available from https://proceedings.mlr.press/v306/banihashem26c.html.

Related Material