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.

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

Dynamic Algorithms for Submodular Maximization with a p-Matchoid Constraint

  • Luying Ma,
  • Yuanyuan Qiang,
  • Bin Liu

摘要

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.