\frac{1}{m}\sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(1)} \cup S_i^{(1)}) \, , \, \frac{1}{m} \sum_{i=1}^m f_i ({S_{\rm{tr}}}^{(2)} \cup S_i^{(2)}) \Bigr\} \geq 0.53 \times {\rm{OPT}}.$$

Check Appendix \[sec:proof\_of\_main\_thm\].

Note that for all the results in Propositions \[alg1lemma\] and \[alg2lemma\] as well as Theorem \[thm:meta-greedy\], for given output sets ${S_{\rm{tr}}}$ or $\{S_i\}_{i=1}^m$, the value of $\frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i)$ is a lower bound for the objective function value of Problem evaluated at the output set ${S_{\rm{tr}}}$. To be more precise, the accurate measure for evaluating the quality of the output set ${S_{\rm{tr}}}$ is $\frac{1}{m}\sum_{i=1}^m\;  \left[\max_{S_i\in V, |S_i|\leq k-l} f_i({S_{\rm{tr}}}\cup S_i)\right]$ which is indeed larger than $\frac{1}{m} \sum_{i=1}^m f_i({S_{\rm{tr}}}\cup S_i)$. Hence, all the guarantees that have obtained in the statements above (as well as Theorem \[thm: randomized meta\] below) would directly translate into the same guarantees when we evaluate the objective in on the set ${S_{\rm{tr}}}$.

Randomized Algorithm
--------------------

In this section, we consider greedy procedures in which the decision to alternate between the set ${S_{\rm{tr}}}$ (the outer maximization) and the sets $\{S_i\}_{i=1}^m$ (the inner maximization) is done based on a randomized scheme. The `Randomized meta-Greedy` procedure, outlined in Algorithm \[alg: Randomized meta-Greedy\], provides a specific randomized order. In each round, with probability $l/k$ we choose to perform 