Non-monotone Submodular Optimization: p-Matchoid Constraints and Fully Dynamic Setting

Submodular maximization subject to a p-matchoid constraint has various applications in machine learning, particularly in tasks such as feature selection, video and text summarization, movie recommendation, graph-based learning, and constraintbased optimization. We study this problem in the dynamic setting, where a sequence of insertions and deletions of elements to a p-matchoid M(V,I) occurs over time and the goal is to efficiently maintain an approximate solution. We propose a dynamic algorithm for non-monotone submodular maximization under a p-matchoid constraint. For a p-matchoid M(V,I) of rank k, defined by a collection of m matroids, our algorithm guarantees a (2p +2 p p(p +1) +1 +ϵ)-approximate solution at any time t in the update sequence, with an expected amortized query complexity of O(ϵ 3 pk4 log2(k)) per update.