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 constraint-based optimization. We study this problem in the dynamic setting, where a sequence of insertions and deletions of elements to a $p$-matchoid $\mathcal{M}(\mathcal{V},\mathcal{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 $\mathcal{M}(\mathcal{V},\mathcal{I})$ of rank $k$, defined by a collection of $m$ matroids, our algorithm guarantees a $(2p+2\sqrt{p(p+1)}+1+ϵ)$-approximate solution at any time $t$ in the update sequence, with an expected amortized query complexity of $O({ϵ}^{-3}p{k}^4{\log }^2(k))$ per update.