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].

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Dynamic Algorithms for Non-monotone Submodular Maximization

  • Yuanyang Liu,
  • Wenguo Yang

摘要

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].