a greedy update on ${S_{\rm{tr}}}$, and with probability $1-l/k$ we choose to perform a greedy update on *all* the $S_i$’s, $i=1, \cdots,m$. This procedure continues until either ${S_{\rm{tr}}}$ or $\{S_i\}_{i=1}^m$ hit their corresponding carnality constraint, in which case we continue to update the other set(s) greedily until they also become full.

**Initialize** the sets ${S_{\rm{tr}}}$ and $\{S_i\}_{i=1}^m$ to the empty set. $e^{*}_i \xleftarrow{} \operatorname*{arg\,max}_{ e\in V}  f_i({S_{\rm{tr}}}\cup S_i\cup\{e\})-f_i({S_{\rm{tr}}}\cup S_i)$ $e^{*}_{tr} \xleftarrow{} \operatorname*{arg\,max}_{ e\in V} \sum_{i=1}^{m} f_i({S_{\rm{tr}}}\cup S_i\cup\{e\})-f_i({S_{\rm{tr}}}\cup S_i)$ **w.p. $\frac{l}{k}$:** ${S_{\rm{tr}}}={S_{\rm{tr}}}\cup\{e^{*}_{tr}\}$ **w.p. $\frac{k-l}{k}$:** $S_i=S_i\cup\{e_i^{*}\}$, $\forall i = 1, \cdots, m$ **end** If ${S_{\rm{tr}}}$ or $S_i$’s have not yet reached their cardinality limit then fill them greedily until their limit is reached Return ${S_{\rm{tr}}}$ and $S_i$

The randomized update of Algorithm \[alg: Randomized meta-Greedy\] is designed to optimally connect the expected increase the objective value at each round with the gap to OPT (as shown in the proof of Theorem \[thm: randomized meta\]). Hence, the `Randomized meta-Greedy` procedure is able to achieve in expectation a guarantee close to the tight value $(1-1/e)\text{OPT}$. However, due to the randomized nature of the algorithm, the sets ${S_{\rm{tr}}}$ or $S_i$ might hit their carnality constraint earlier than expected. Analyzing the function value at this “stopping 