The Power of Subsampling in Submodular Maximization

We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present S ample G reedy , which obtains a ( p + 2 + o ( 1 ) ) -approximation for maximizing a submodular function subject to a p -extendible system using O ( n + n k / p ) evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p + 1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present S ample- S treaming , which obtains a ( 4 p + 2 − o ( 1 ) ) -approximation for maximizing a submodular function subject to a p -matchoid using O ( k ) memory and O ( k m / p ) evaluation and feasibility queries per element, and m is the number of matroids defining the p -matchoid. The approximation ratio improves to 4 p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.