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 → ℝ + 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.

Authors

• Kiarash Banihashem
• Leyla Biabani
• Samira Goudarzi
• MohammadTaghi Hajiaghayi
• Peyman Jabbarzade
• Morteza Monemizadeh

Keywords

No keywords are indexed for this paper.