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 M ( V , I ) occurs over time and the goal is to e ffi ciently 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 (2 p + 2 (cid:112) p ( p + 1) + 1 + ϵ )-approximate solution at any time t in the update sequence, with an expected amortized query complexity of O ( ϵ − 3 pk 4 log 2 ( k )) per update.