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

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.