Dynamic Algorithms for Non-monotone Submodular Maximization
摘要
Submodular maximization is a classical problem with many applications of machine learning, combinatorial optimization and so on. In recent years, there is an increasing concern on the submodular maximization problem in the dynamic setting. After the first dynamic algorithms for the submodular maximization problem was developed in 2020, Chen and Peng [3] raised an open question in 2022, asking for the possibility to extend some results from dynamic monotone submodular maximization to non-monotone cases. In this paper, we consider the problems of dynamic non-monotone non-negative submodular maximization under the cardinality and matroid constraints. We answer the open question by developing the first algorithm for non-monotone submodular maximization under the matroid constraint. We derived a randomized algorithm maintaining an \((1-\epsilon )/(8+e)\) -approximate of the solution. The algorithm requires \(O(k^2\epsilon ^{-1}\log (k)\log ^3(k/\epsilon ))\) amortized oracle queries. As a byproduct, we also improved the algorithm for non-monotone submodular maximization under the cardinality constraint, maintaining an approximation guarantee of \(1/(6+\epsilon )\) and requiring \(O(k^2\epsilon ^{-1}\log ^2(k))\) amortized oracle queries which was originally developed by K. Banihashem et al. [5].