Dynamic Algorithms for Submodular Maximization with a p-Matchoid Constraint
摘要
Submodular maximization has been increasingly used in multiple applications of machine learning and data mining. Moreover, there has been a growing interest in both submodular maximization and dynamic algorithms. Previous work has considered dynamic algorithms for submodular functions under the cardinality constraint and the matroid constraint. In this paper, we consider the problem of maximizing a monotone submodular set function \(f:2^{\mathcal {N} } \rightarrow \mathbb {R} ^{+}\) subject to the p-matchoid constraint in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that obtains a 4p-approximate solution and maintains an efficient data structure with a \(\tilde{O} (k^{2} )\) amortized update time, where k is an upper bound on the cardinality of the feasible solution.