Dynamic Algorithms for Matroid Submodular Maximization

Abstract

Submodular maximization under matroid and cardinality constraints are classical problems with a wide range of applications in machine learning, auction theory, and combinatorial optimization. In this paper, we consider these problems in the dynamic setting, where (1) we have oracle access to a monotone submodular function $f:2^V\to {\mathbb{R}}^{+}$ and (2) we are given a sequence $\mathcal{S}$ of insertions and deletions of elements of an underlying ground set $V$. We develop the first fully dynamic $(4+\epsilon )$-approximation algorithm for the submodular maximization problem under the matroid constraint using an expected worst-case $O(k\log (k){\log }^3(k/\epsilon ))$ query complexity where $0<\epsilon \le 1$. This resolves an open problem of Chen and Peng (STOC'22) and Lattanzi et al. (NeurIPS'20). As a byproduct, for the submodular maximization under the cardinality constraint $k$, we propose a parameterized (by the cardinality constraint $k$) dynamic algorithm that maintains a $(2+\epsilon )$-approximate solution of the sequence $\mathcal{S}$ at any time $t$ using an expected worst-case query complexity $O(k{\epsilon }^{-1}{\log }^2(k))$. This is the first dynamic algorithm for the problem that has a query complexity independent of the size of ground set $V$.