Dynamic Algorithms for Matroid Submodular Maximization
share
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 𝒮 of insertions and deletions of elements of an underlying ground set V. We develop the first parameterized (by the rank k of a matroid ℳ) dynamic (4+ϵ)-approximation algorithm for the submodular maximization problem under the matroid constraint using an expected worst-case O(klog(k)log^3(k/ϵ)) query complexity where 0 < ϵ≤ 1. Chen and Peng 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. (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 𝒮 at any time t using the expected amortized worst-case complexity O(kϵ^-1log^2(k)). This is the first dynamic algorithm for the problem that has a query complexity independent of the size of ground set V.
READ FULL TEXT