$\beta$, and not just cases that $\beta$ is small or large. Similarly, we can provide near-optimality guarantees for Algorithm \[alg: Reverse discrete meta-Greedy\].

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

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

Similarly, we can show that $\gamma=\text{OPT}/2$ leads to (the worst) guarantee $1/2$-OPT, while for large and small values of $\gamma$ the bound in Proposition \[alg2lemma\] approaches the optimal approximation $(1-1/e)\text{OPT}$.

We note that the values $\beta$ in Proposition \[alg1lemma\] (Algorithm \[alg: discrete meta-Greedy\]) and $\gamma$ in Proposition \[alg2lemma\] (Algorithm \[alg: Reverse discrete meta-Greedy\]) represent two different extremes. The value $\beta$ represents the significance of the role of ${S_{\rm{tr}}}$ in solving Problem , and $\gamma$ represents how significant the role of the sets $\{S_i\}_{i=1}^m$ can be. Even though the worst-case guarantees of Propositions \[alg1lemma\] and \[alg2lemma\] are obtained when $\beta, \gamma = \text{OPT}/2$, a coupled analysis 