On the Complexity of Dynamic Submodular Maximization
This work addresses the computational limits of dynamic algorithms for submodular optimization, which is important for machine learning and data stream applications, but it is incremental as it builds on prior dynamic algorithms.
The paper tackles the problem of dynamic submodular maximization under insertions and deletions, showing that achieving a (0.5+ε)-approximation requires polynomial amortized query complexity, while for insertion-only streams, it presents efficient algorithms with (1-1/e-ε)-approximation and specified query complexities.
We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of $n$ insertions and deletions. We show that any algorithm that maintains a $(0.5+ε)$-approximate solution under a cardinality constraint, for any constant $ε>0$, must have an amortized query complexity that is $\mathit{polynomial}$ in $n$. Moreover, a linear amortized query complexity is needed in order to maintain a $0.584$-approximate solution. This is in sharp contrast with recent dynamic algorithms of [LMNF+20, Mon20] that achieve $(0.5-ε)$-approximation with a $\mathsf{poly}\log(n)$ amortized query complexity. On the positive side, when the stream is insertion-only, we present efficient algorithms for the problem under a cardinality constraint and under a matroid constraint with approximation guarantee $1-1/e-ε$ and amortized query complexities $\smash{O(\log (k/ε)/ε^2)}$ and $\smash{k^{\tilde{O}(1/ε^2)}\log n}$, respectively, where $k$ denotes the cardinality parameter or the rank of the matroid.