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

Non-monotone submodular maximization is a fundamental problem in machine learning and combinatorial optimization, with a range of applications including text and video summarization, recommendation systems, feature selection, Max Cut problems in graphs, and viral marketing strategies. In this work, we study non-monotone submodular maximization under a cardinality constraint $k$ in the fully dynamic setting, and obtain results that improve upon the previously established 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). We present a dynamic algorithm that achieves a $0.262$-approximation with worst-case expected update time $O(\epsilon^{-3}\log(k)\log(\epsilon^{-1}k) + \epsilon^{-2}k^2\log(k))$, where $0 < \epsilon \leq 1$ is the error parameter. We also obtain another dynamic algorithm with update time bounded by $\text{poly}(\epsilon^{-1}, k)$ that achieves a $0.277$-approximation guarantee.