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. Theorem 1 Suppose we start with an empty set V. Let us first consider the offline scenario. We later show how to handle insertion and deletion of elements. Our algorithm (that we call it Algorithm Sampling) is a refinement of Algorithm [LV19]. OP T. We prove it in this section for the sake of completeness.