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 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 (4+)-approximation algorithm for the submodular maximization problem under the matroid constraint using an expected worst-case O(k(k)^3(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^-1^2(k)). This is the first dynamic algorithm for the problem that has a query complexity independent of the size of ground set V.

Tasks

Reproductions