Dynamic Submodular Maximization (Supplementary Material) Morteza Monemizadeh Department of Mathematics and Computer Science TU Eindhoven, the Netherlands m.monemizadeh@tue.nl

In this section we prove the following theorem. Let us first consider the offline scenario. We later show how to handle insertion and deletion of elements. We prove it in this section for the sake of completeness. Let R be the set of points that survive after the filtering step.