Dynamic Submodular Maximization

One of the basic primitives in the class of submodular optimization problems is the submodular maximization under a cardinality constraint. Here we are given a ground set $V$ that is endowed with a monotone submodular function $f: 2^V \rightarrow \REAL^+$ and a parameter $0 < k \le n$ and the goal is to return an optimal set $S \subseteq V$ of at most $k$ elements, i.e., $f(S)$ is maximum among all subsets of $V$ of size at most $k$. This basic primitive has many applications in machine learning as well as combinatorial optimization. Example applications are agglomerative clustering, exemplar-based clustering, categorical feature compression, document and corpus summarization, recommender systems, search result diversification, data subset selection, minimum spanning tree, max flow, global minimum cut, maximum matching, traveling salesman problem, max clique, max cut, set cover and knapsack, among the others. In this paper, we propose the first dynamic algorithm for this problem. Given a stream of inserts and deletes of elements of an underlying ground set $V$, we develop a dynamic algorithm that with high probability, maintains a $(\frac{1}{2} - \epsilon)$-approximation of a cardinality-constrained monotone submodular maximization for any sequence of $z$ updates (inserts and deletes) in time $O(k^2z\epsilon^{-3}\cdot \log^5 n)$, where $n$ is the maximum size of $V$ at any time. That is, the amortized update time of our algorithm is $O(k^2\epsilon^{-3}\cdot \log^5 n)$.