Dynamic Algorithms for Matroid Submodular Maximization

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: 2V rightarrow ℝ^+ and (2) we are given a sequence S of insertions and deletions of elements of an underlying ground set V. We develop the first fully dynamic (4+ε)-approximation algorithm for the submodular maximization problem under the matroid constraint using an expected worst-case O(klog(k)log3(k/ε)) query complexity where 0 < ε ≤ 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+ε)-approximate solution of the sequence S at any time t using an expected worst-case query complexity O(kε-1log2(k)). This is the first dynamic algorithm for the problem that has a query complexity independent of the size of ground set V.