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: 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.