and chooses the solution set that has the higher objective function value. Note that as we described earlier, the main output of this procedure should be the set ${S_{\rm{tr}}}$ of size $l$. Hence, the output of `Meta-Greedy` is either ${S_{\rm{tr}}}^{(1)}$ or ${S_{\rm{tr}}}^{(2)}$ and the sets $ \{S_i^{(1)}\}_{i=1}^m$ and $ \{S_i^{(2)}\}_{i=1}^m$ are only evaluated for the purpose of comparing objective function values.

Next, we explain why our $\texttt{Meta-Greedy}$ method can outperform both Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\]. This will be done by providing the theoretical guarantees for these methods and consequently explaining why Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] are complementary.

Run Algorithms \[alg: discrete meta-Greedy\] and \[alg: Reverse discrete meta-Greedy\] and obtain respective solution sets ${S_{\rm{tr}}}^{(1)}, \{S_i^{(1)}\}_{i=1}^m$ and ${S_{\rm{tr}}}^{(2)}, \{S_i^{(2)}\}_{i=1}^m$.

Compute the objective value $ \sum_{i=1}^{m}f_i({S_{\rm{tr}}}\cup S_i)$ for both solution sets.

**Theoretical guarantees.** We begin with the analysis of Algorithm \[alg: discrete meta-Greedy\]. The following proposition relates the overall performance of Algorithm \[alg: discrete meta-Greedy\] to its performance after phase 1 and shows that the output of the algorithm is at least $1/2$-optimal. We use OPT for the optimal value of Problem .

\[alg1lemma\] Let ${S_{\rm{tr}}}^{(1)}, \{S_i^{(1)}\}_{i=1}^m$ be the output of Algorithm \[alg: 