When Streaming Fails: Dynamic Algorithms for Unconstrained Submodular Maximization

Dynamic submodular optimization has attracted significant attention in recent years, with a growing body of work studying both monotone and non-monotone variants under various constraints. A key insight underlying much of this progress is that the dynamic setting is closely related to the streaming setting, both in terms of algorithms and lower bounds. This raises a natural and fundamental question: \emph{can we obtain dynamic algorithms even for problems where no streaming analogue exists?} In this paper, we answer this question affirmatively for the fundamental problem of Unconstrained Submodular Maximization (USM). Unlike other variants of submodular maximization, no streaming algorithm with non-trivial guarantees is known for USM. In the dynamic setting, a trivial $0.25$-approximation follows from random sampling, but obtaining any better approximation with sublinear update time had remained open. We present the first dynamic algorithms for USM that break the $0.25$-approximation barrier while maintaining sublinear update time, across several natural dynamic models: incremental updates, decremental updates with known deletion order, and fully dynamic updates with known deletion times.