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 : 2 V → R + 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 algorithm for the submodular maximization problem under the matroid constraint that maintains a (4 + ϵ)-approximation solution (0 < ϵ ≤ 1) using an expected query complexity of O(k log(k) log 3 (k/ϵ)) , which is indeed parameterized by the rank k of the matroid M(V, I) as well.

Chen and Peng [52] at STOC'22 studied the complexity of this problem in the insertion-only dynamic model (a restricted version of the fully dynamic model where deletion is not allowed), and they raised the following important open question: "for fully dynamic streams [sequences of insertions and deletions of elements], there is no known constant-factor approximation algorithm with poly(k) amortized queries for matroid constraints." Our dynamic algorithm answers this question as well as an open problem of Lattanzi et al. [109] (NeurIPS'20) affirmatively.

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 query complexity of O(kϵ -1 log 2 (k)), which is an improvement upon the dynamic algorithm that Monemizadeh [125] (NeurIPS'20) developed for this problem using an expected query complexity O(k 2 ϵ -3 log 5 (n)). In particular, this dynamic algorithm is the first one for this problem whose query complexity is independent of the size of ground set V (i.e., n = |V|).

We develop our dynamic algorithm for the submodular maximization problem under the matroid or cardinality constraint by designing a randomized leveled data structure that supports insertion and deletion operations, maintaining an approximate solution for the given problem. In addition, we develop a fast construction algorithm for our data structure that uses a one-pass over a random permutation of the elements and utilizes monotonicity property of our problems which has a subtle proof in the matroid case. We believe these techniques could also be useful for other optimization problems in the area of dynamic algorithms.