discrete meta-Greedy\], and define $\beta$ as $\beta :=\frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}^{(1)})$. If the set functions $f_i$ are monotone and submodular, then $$\frac{1}{m} \sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(1)} \cup S_i^{(1)}) 
    \geq \max \Bigl\{ \beta \,, \, (1-1/e)({\rm{OPT}} - 2 \beta) + \beta \Bigr \}.$$ Consequently, the solution obtained by Algorithm \[alg: discrete meta-Greedy\] is at least $1/2$-optimal for any value of $\beta$.

Check Appendix \[sec:proof\_prop\_1\].

The proof of this proposition is relegated to the appendix. The key step in the proof is to relate the progress made in phase 1 to the gap to OPT. This is indeed challenging as phase 1 only involves updates on the outer maximization of . In this regard, we prove a novel technical lemma that can be generally applicable to any mini-max submodular problem. The guarantee given in Proposition \[alg1lemma\] is minimized when $\beta = \text{OPT}/2$. If $\beta$ is small (e.g., $\beta = 0$) or if $\beta$ is large (e.g. if $\beta = (1-1/e)\text{OPT}$) then the guarantee becomes tight (e.g. $(1-1/e)\text{OPT})$. This is indeed expected from the greedy nature of the two phases of Algorithm \[alg: discrete meta-Greedy\]. What is non-trivial about the result of Proposition \[alg1lemma\] is that it provides a strong guarantee for any value of 