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

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.

Many important decisions involve selecting a diverse and valuable set of items under a budget — for example, choosing which news articles to recommend or which sensors to activate. This is called submodular maximization. The challenge is that the data keeps changing: items are added and removed over time, so we need algorithms that can update the solution quickly without starting from scratch. Previous dynamic algorithms could handle such changes, but they offered either low accuracy or required very slow updates. In this work, we design new dynamic algorithms that are both fast and accurate. Our best method achieves nearly 28% of the optimal value while processing each update in time that scales polynomially with the budget and desired accuracy. Our research makes it practical to maintain high-quality solutions in real-time as data evolves. This is useful for applications like real-time recommendation systems, monitoring sensor networks, or any setting where good decisions must be made quickly from continuously changing information.