Abstract
Submodular maximization under matroid and cardinality constraints areclassical problems with a wide range of applications in machine learning,auction theory, and combinatorial optimization. In this paper, we considerthese problems in the dynamic setting where (1) we have oracle access to amonotone submodular function $f: 2^{V} \rightarrow \mathbb{R}^+$ and (2) we aregiven a sequence $\mathcal{S}$ of insertions and deletions of elements of anunderlying ground set $V$. We develop the first parameterized (by the rank $k$ of a matroid$\mathcal{M}$) dynamic $(4+\epsilon)$-approximation algorithm for thesubmodular maximization problem under the matroid constraint using an expectedworst-case $O(k\log(k)\log^3{(k/\epsilon)})$ query complexity where $0 <\epsilon \le 1$. Chen and Peng at STOC'22 studied the complexity of thisproblem in the insertion-only dynamic model (a restricted version of the fullydynamic model where deletion is not allowed), and they raised the followingimportant open question: *"for fully dynamic streams [sequences of insertionsand deletions of elements], there is no known constant-factor approximationalgorithm with poly(k) amortized queries for matroid constraints."* Our dynamicalgorithm answers this question as well as an open problem of Lattanzi et al.(NeurIPS'20) affirmatively. As a byproduct, for the submodular maximization under the cardinalityconstraint $k$, we propose a parameterized (by the cardinality constraint $k$)dynamic algorithm that maintains a $(2+\epsilon)$-approximate solution of thesequence $\mathcal{S}$ at any time $t$ using the expected amortized worst-casecomplexity $O(k\epsilon^{-1}\log^2(k))$. This is the first dynamic algorithmfor the problem that has a query complexity independent of the size of groundset $V$.